POJ 3470: Wall

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;
}