Submission #158479

#	Time	Username	Problem	Language	Result	Execution time	Memory
158479		maruii	조개 줍기 (KOI17_shell)	C++14	100 / 100	619 ms	35748 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) {
	ye[x] = y;
	while (1) {
		int t = 0;
		if ((c > 0 && y < N && query(x, y + 1) == query(x, y) + A[x][y + 1]) || (c < 0 && y < N && query(x, y + 1) != query(x - 1, y + 1) + A[x][y + 1])) y++;
		else x++;
		if (x > N) break;
		ye[x] = y;
	}
}
 
 
void lo(int x, int y, int c) {
	ys[x] = y;
	while (1) {
		int t = 0;
		if ((c > 0 && x < N && query(x + 1, y) == query(x, y) + A[x + 1][y]) || (c < 0 && x < N && query(x + 1, y) != query(x + 1, y - 1) + A[x + 1][y])) x++;
		else y++;
		if (y > N || ye[x] < y) break;
		ys[x] = min(ys[x], 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];
	}
 
	printf("%lld\n", cost);
	ys[N + 1] = 1;
	for (int T = 0; T < N; ++T) {
		char c; int x, y; cin >> c >> x >> y;
		fill(ys + x, ys + N + 1, N + 1);
		fill(ye + x, ye + N + 1, 0);
		int t = c == 'U' ? 1 : -1;
		up(x, y, t);
		lo(x, y, t);
		for (int i = x; ys[i] <= ye[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;
}

Compilation message (stderr)

shell.cpp: In function 'void up(int, int, int)':
shell.cpp:28:7: warning: unused variable 't' [-Wunused-variable]
   int t = 0;
       ^
shell.cpp: In function 'void lo(int, int, int)':
shell.cpp:40:7: warning: unused variable 't' [-Wunused-variable]
   int t = 0;
       ^

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