4223번: Mummy Madness

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


시간복잡도는 테스트 케이스마다 $O(n\lg L * (\lg L+\lg n))$

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int MX = 1e6;
struct st {
    int x, l, r, c;
}line[200000];
int n, x[100000], y[100000], len[MX * 8], cnt[MX * 8];
void update(int h, int l, int r, int gl, int gr, int x) {
    if (gr < l || r < gl) return;
    if (gl <= l&&r <= gr) cnt[h] += x;
    else update(h * 2 + 1, l, (l + r) / 2, gl, gr, x), update(h * 2 + 2, (l + r) / 2 + 1, r, gl, gr, x);
    len[h] = cnt[h] ? r - l + 1 : l^r ? len[h * 2 + 1] + len[h * 2 + 2] : 0;
}
bool f(int t) {
    int sz = 0;
    for (int i = 0; i < n; i++) {
        int sx = max(x[i] - t, MX - t), ex = min(x[i] + t, MX + t),
            sy = max(y[i] - t, MX - t), ey = min(y[i] + t, MX + t);
        if (sx > ex || sy > ey) continue;
        line[sz++] = { sx,sy,ey,1 };
        line[sz++] = { ex + 1,sy,ey,-1 };
    }
    sort(line, line + sz, [](st i, st j) {return i.x < j.x; });
    long long area = 0;
    for (int i = 0; i < sz; i++) {
        if (i) area += 1LL * len[0] * (line[i].x - line[i - 1].x);
        update(0, 0, MX * 2 + 1, line[i].l, line[i].r, line[i].c);
    }
    return area < 4LL * t*t + 4 * t + 1;
}
int main() {
    for (int t = 1; scanf("%d", &n), ~n; t++) {
        for (int i = 0; i < n; i++) {
            scanf("%d%d", x + i, y + i);
            x[i] += MX;
            y[i] += MX;
        }
        int low = 0, up = MX, mid;
        while (low <= up) {
            mid = (low + up) / 2;
            f(mid) ? low = mid + 1 : up = mid - 1;
        }
        printf("Case %d: ", t);
        low > MX ? puts("never") : printf("%d\n", low);
    }
    return 0;
}