3433번: Hanging Hats

https://www.acmicpc.net/problem/3433

#include<cstdio>
#include<map>
#include<algorithm>
#include<vector>
using namespace std;
const int MXN = 1e5;
typedef long long ll;
int z, n;
ll x[MXN], y[MXN];
char c[MXN];
map<ll, ll> mp[2];
struct st {
    ll u, v;
    int idx;
    bool operator<(st i) const {
        return u<i.u || u == i.u&&v>i.v;
    }
};
void add(ll u, ll v, int t) {
    for (map<ll, ll>::iterator it = mp[t].lower_bound(u); it != mp[t].end() && it->second <= v;) mp[t].erase(it++);
    mp[t][u] = v;
}
int ck[MXN], r[MXN], szn, szw, midx[MXN], bitn[MXN + 1], bitw[MXN + 1];
int main() {
    for (scanf("%d", &z); z--;) {
        mp[0].clear();
        mp[1].clear();
        scanf("%d", &n);
        szn = szw = 0;
        fill(ck, ck + n, 0);
        fill(r, r + n, 0);
        fill(midx, midx + n, 1e9);
        fill(bitn + 1, bitn + n + 1, 1e9);
        fill(bitw + 1, bitw + n + 1, 1e9);
        vector<st> vn, vw;
        map<ll, int> mpn, mpw;
        for (int i = 0; i < n; i++) {
            scanf("%lld%lld %c", x + i, y + i, c + i);
            auto it0 = mp[0].upper_bound(x[i] - y[i]), it1 = mp[1].upper_bound(2 * x[i] - y[i]);
            if (it0 != mp[0].begin() && (--it0)->second >= x[i] + y[i] || it1 != mp[1].begin() && (--it1)->second >= 2 * x[i] + y[i]) ck[i] = 1;
            else {
                c[i] == 'W' ? add(x[i] - y[i], x[i] + y[i], 0) : add(2 * x[i] - y[i], 2 * x[i] + y[i], 1);
                mpw[x[i] + y[i]] = mpn[2 * x[i] + y[i]] = 0;
                vw.push_back({ x[i] - y[i],x[i] + y[i],i });
                vn.push_back({ 2 * x[i] - y[i],2 * x[i] + y[i],i });
            }
        }
        sort(vw.begin(), vw.end());
        sort(vn.begin(), vn.end());
        for (auto &it : mpw) it.second = ++szw;
        for (auto &it : mpn) it.second = ++szn;
        for (auto it : vw) {
            for (int j = mpw[it.v]; j <= szw; j += j&-j) midx[it.idx] = min(midx[it.idx], bitw[j]);
            if (c[it.idx] == 'W') for (int j = mpw[it.v]; j; j -= j&-j) bitw[j] = min(bitw[j], it.idx);
        }
        for (auto it : vn) {
            for (int j = mpn[it.v]; j <= szn; j += j&-j) midx[it.idx] = min(midx[it.idx], bitn[j]);
            if (c[it.idx] == 'N') for (int j = mpn[it.v]; j; j -= j&-j) bitn[j] = min(bitn[j], it.idx);
        }
        for (int i = 0; i < n; i++) if (!ck[i]) {
            r[i]++;
            if (midx[i] < 1e9) r[midx[i]]--;
        }
        for (int i = 0, s = 0; i < n; i++) {
            if (ck[i]) puts("FAIL");
            else printf("%d\n", s += r[i]);
        }
    }
    return 0;
}