题解 CF555C 【Case of Chocolate】

2019-03-30 09:38:04


观察样例,发现格子被吃之后会被分割成这样几种形状:

1. 跟原来长得一样
# # # # #
# # # # 
# # #
# #
#
-----------

2.1 比原来多出一块(前几行):
# # # # #
# # # # #
# # # # #
# # # #
# # #
# #
#
-----------

2.2 比原来多出一块(前几列):

# # # # # #
# # # # #
# # # #
# # #
-----------

3. 比原来多出两块:
# # # # # # #
# # # # # # #
# # # # # # #
# # # # # #
# # # # #
# # # #
# # #
-----------

4. 某些矩形,肯定不会再被吃到

这样一来,一块区域就可以用四个量来表示:左右边界,向上和向左延伸的长度

用set维护即可:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>

using namespace std;

int n, m, ans;

class Squares
{
public:
    int l, r;
    int len_l, len_u;
    Squares()
    {
        l = r = 0;
        len_l = len_u = 0;
    }
    Squares(int _l, int _r, int _len_l, int _len_u)
    {
        l = _l, r = _r;
        len_l = _len_l, len_u = _len_u;
    }
    bool operator < (const Squares &b)const
    {
        return r < b.r;
    }
} a, res, nxt;

set<Squares> s;
set<Squares>::iterator it;

inline int read()
{
    char ch = getchar();
    int ret = 0, f = 1;
    while (ch > '9' || ch < '0')
    {
        if (ch == '-')
            f = -f;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
        ret = ret * 10 + ch - '0', ch = getchar();
    return ret * f;
}

int main()
{
    // freopen("test.in", "r", stdin);
    // freopen("test.out", "w", stdout);
    n = read(), m = read();
    res = Squares(1, n, 0, 0);
    s.insert(res);
    while (m--)
    {
        int x = read(), y = read();
        char ch = getchar();
        while (ch != 'U' && ch != 'L')
            ch = getchar();
        a = Squares(x, x, 0, 0);
        it = s.lower_bound(a);
        if (it == s.end() || it->l > x || it->r < x)
        {
            printf("0\n");
            continue;
        }
        res = *it;
        s.erase(it);
        if (ch == 'U')
        {
            ans = res.r - x + 1 + res.len_u;
            printf("%d\n", ans);
            if (x != res.l)
            {
                nxt = Squares(res.l, x - 1, res.len_l, ans);
                s.insert(nxt);
            }
            if (x != res.r)
            {
                nxt = Squares(x + 1, res.r, 0, res.len_u);
                s.insert(nxt);
            }
        }
        else
        {
            ans = x - res.l + 1 + res.len_l;
            printf("%d\n", ans);
            if (x != res.l)
            {
                nxt = Squares(res.l, x - 1, res.len_l, 0);
                s.insert(nxt);
            }
            if (x != res.r)
            {
                nxt = Squares(x + 1, res.r, ans, res.len_u);
                s.insert(nxt);
            }
        }
    }
    return 0;
}