Submission #158470

#	Time	Username	Problem	Language	Result	Execution time	Memory
158470		maruii	조개 줍기 (KOI17_shell)	C++14	0 / 100	171 ms	20228 KiB

shell

#include <bits/stdc++.h>
using namespace std;

int N, f[1505][1505], A[1505][1505], ys[1505], ye[1505];

struct BIT {
	int A[1505];
	void update(int x, int v) {
		x++;
		for (; x; x -= x & -x) A[x] += v;
	}
	void update(int s, int e, int v) {
		update(e, v);
		update(s - 1, -v);
	}
	int query(int x) {
		x++;
		int ret = 0;
		for (; x < 1505; x += x & -x) ret += A[x];
		return ret;
	}
} fen[1505];

inline int query(int x, int y) { return f[x][y] + fen[x].query(y); }
void up(int x, int y, int c) {
	while (1) {
		int t = 0;
		if (c > 0) while (y + 1 <= N && query(x, y + 1) == query(x, y) + A[x][y + 1]) y++, t = 1;
		else while (y + 1 <= N && query(x, y + 1) != query(x - 1, y + 1) + A[x][y + 1]) y++, t = 1;
		ye[x] = y;
		if (x == N || (c > 0 && query(x + 1, y) != query(x, y) + A[x + 1][y]) || (c < 0 && query(x + 1, y) != query(x + 1, y - 1) + A[x + 1][y])) {
			if (t == 0) break;
			continue;
		}
		x++;
	}
}


void lo(int x, int y, int c) {
	ys[x] = y;
	while (1) {
		int t = 0;
		if (c > 0) while (x + 1 <= N && query(x + 1, y) == query(x, y) + A[x + 1][y]) ys[++x] = y, t = 1;
		else while (x + 1 <= N && query(x + 1, y) != query(x + 1, y - 1) + A[x + 1][y]) ys[++x] = y, t = 1;
		if (y == N || (c > 0 && query(x, y + 1) != query(x, y) + A[x][y + 1]) || (c < 0 && query(x, y + 1) != query(x - 1, y + 1) + A[x][y + 1])) {
			if (t == 0) break;
			continue;
		}
		y++;
	}
}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> N;
	long long cost = 0;
	for (int i = 1; i <= N; ++i) for (int j = 1; j <= N; ++j) {
		cin >> A[i][j];
		f[i][j] = A[i][j] + max(f[i - 1][j], f[i][j - 1]);
		cost += f[i][j];
	}
	for (int i = 1; i <= N; ++i) f[0][i] = f[i][0] = -1e9;

	printf("%lld\n", cost);
	for (int T = 0; T < N; ++T) {
		char c; int x, y; cin >> c >> x >> y;
		fill(ys + x, ys + N + 1, 0);
		int t = c == 'U' ? 1 : -1;
		up(x, y, t);
		lo(x, y, t);
		for (int i = x; ys[i]; ++i) {
			fen[i].update(ys[i], ye[i], t);
			cost += t * (ye[i] - ys[i] + 1);
		}
		A[x][y] += t;
		printf("%lld\n", cost);
	}
	return 0;
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 34
• Subtask 3: 0 / 54