http://poj.org/problem?id=3470
平面走査するだけのタイピングゲーなんだけど、TLEがかなり厳しい。AC率308/2036が物語っている。
vectorを配列にするとかベタな高速化をしてもACに至らず…segtreeが重いのかな?
TLE解法
struct T { pi v; T(pi v = pi(inf, -1)) : v(v) {} T operator+(const T& t) {//when getting value return T(min(v, t.v)); } void operator+=(const T& t) {//when updating value v = t.v; } }; struct segtree { int n; T sum[MAX_V], lazy[MAX_V]; void init(int mx) { n = 1; while(n < mx) n *= 2; fill(sum, sum + n * 2, T()); fill(lazy, lazy + n * 2, T()); } segtree(int mx = 0) { init(mx); } inline void lazy_eval(int k, int l, int r) { if(lazy[k].v != T().v) { sum[k * 2 + 1] += lazy[k]; lazy[k * 2 + 1] += lazy[k]; sum[k * 2 + 2] += lazy[k]; lazy[k * 2 + 2] += lazy[k]; lazy[k] = T(); } } void app(int a, int b, T s, int k, int l, int r) { if(b <= l || r <= a) return; if(a <= l && r <= b) { sum[k] += s; //here too lazy[k] += s; } else { lazy_eval(k, l, r); app(a, b, s, k * 2 + 1, l, (l + r) / 2); app(a, b, s, k * 2 + 2, (l + r) / 2, r); sum[k] = sum[k * 2 + 1] + sum[k * 2 + 2]; } } T ga(int a, int b, int k, int l, int r) { if(b <= l || r <= a) return T(); if(a <= l && r <= b) return sum[k]; else { lazy_eval(k, l, r); T lv = ga(a, b, k * 2 + 1, l, (l + r) / 2); T rv = ga(a, b, k * 2 + 2, (l + r) / 2, r); return lv + rv; } } void show() { vector<pi> tmp; rep(i, 0, n) { tmp.push_back(get(i, i + 1)); } debug(tmp); } pi get(int a, int b) { return ga(a, b, 0, 0, n).v; } //[a, b) void update(int a, int b, pi s) { app(a, b, T(s), 0, 0, n); } //[a, b) }; struct query { bool wall; int x1, x2, index; }; int N, M; int X1[MAX_N], Y1[MAX_N], X2[MAX_N], Y2[MAX_N]; int X[MAX_N], Y[MAX_N]; int vx[MAX_N], vy[MAX_N]; segtree seg; vector<query> Q[MAX_N]; pi P[MAX_N][4]; int ans[MAX_N]; int fd(int *V, int n, int a) { return find(V, V + n, a) - V; } void solve(int at) { int n = 0, m = 0; rep(i, 0, N) { vx[n++] = X1[i]; vx[n++] = X2[i]; vy[m++] = Y1[i]; vy[m++] = Y2[i]; vx[n++] = X[i]; vy[m++] = Y[i]; } sort(vx, vx + n); sort(vy, vy + m); n = unique(vx, vx + n) - vx; m = unique(vy, vy + m) - vy; rep(i, 0, m) { Q[i].clear(); } rep(i, 0, N) { int nx1 = fd(vx, n, X1[i]), nx2 = fd(vx, n, X2[i]); int ny1 = fd(vy, m, Y1[i]), ny2 = fd(vy, m, Y2[i]); if(nx1 == nx2) { int ny = max(ny1, ny2); Q[ny].push_back((query){true, nx1, nx1 + 1, i}); } else if(ny1 == ny2) { int nmx = max(nx1, nx2), nmi = min(nx1, nx2); Q[ny1].push_back((query){true, nmi, nmx + 1, i}); } } rep(i, 0, M) { int nx = fd(vx, n, X[i]), ny = fd(vy, m, Y[i]); Q[ny].push_back((query){false, nx, nx + 1, i}); } seg.init(n); rep(i, 0, m) { rep(j, 0, (int)Q[i].size()) { query &q = Q[i][j]; //debug(q.wall, q.x1, q.x2, i, q.index); if(q.wall) { seg.update(q.x1, q.x2, pi(i, q.index)); //seg.show(); } else { pi p = seg.get(q.x1, q.x2); if(p == T().v) { P[q.index][at] = T().v; } else { P[q.index][at] = pi(vy[i] - vy[p.fst], p.sec); } } } } } void neg_flip() { rep(i, 0, N) { X1[i] *= -1; Y1[i] *= -1; X2[i] *= -1; Y2[i] *= -1; } rep(i, 0, M) { X[i] *= -1; Y[i] *= -1; } } void xy_flip() { rep(i, 0, N) { swap(X1[i], Y1[i]); swap(X2[i], Y2[i]); } rep(i, 0, M) { swap(X[i], Y[i]); } } int main() { scanf("%d%d", &N, &M); rep(i, 0, N) { scanf("%d%d%d%d", &X1[i], &Y1[i], &X2[i], &Y2[i]); } rep(i, 0, M) { scanf("%d%d", &X[i], &Y[i]); } int at = 0; solve(at++); neg_flip(); solve(at++); xy_flip(); solve(at++); neg_flip(); solve(at++); rep(i, 0, M) { //debug(P[i]); int at = -1, dist = inf; rep(j, 0, 4) { if(dist > P[i][j].fst) { dist = P[i][j].fst; at = P[i][j].sec; } } ans[at]++; } rep(i, 0, M) { printf("%d\n", ans[i]); } return 0; }