Submission #158465

#	Time	Username	Problem	Language	Result	Execution time	Memory
158465		maruii	조개 줍기 (KOI17_shell)	C++14	0 / 100	201 ms	31292 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];

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


void lo(int x, int y, int c) {
	ys[x] = y;
	while (1) {
		if (c > 0) while (x + 1 <= N && fen[x + 1].query(y) == fen[x].query(y) + A[x + 1][y]) ys[++x] = y;
		else while (x + 1 <= N && fen[x + 1].query(y) != fen[x + 1].query(y - 1) + A[x + 1][y]) ys[++x] = y;
		if (y == N || (c > 0 && fen[x].query(y + 1) != fen[x].query(y) + A[x][y + 1]) || (c < 0 && fen[x].query(y + 1) != fen[x - 1].query(y + 1) + A[x][y + 1])) break;
		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]);
		fen[i].update(j, j, f[i][j]);
		cost += f[i][j];
	}
	for (int i = 1; i <= N; ++i) {
		fen[i].update(0, 0, -1);
		fen[0].update(i, i, -1);
	}

	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