oj.uz

Submission #158471

# Submission time Handle Problem Language Result Execution time Memory
158471 2019-10-17T09:20:06 Z maruii None (KOI17_shell) C++14
46 / 100
 397 ms 35492 KB 
#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) 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];
	}
	for (int i = 1; i <= N; ++i) f[0][i] = f[i][0] = -1e9;

	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

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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1656 KB Output is correct
2 Correct 5 ms 1784 KB Output is correct
3 Correct 5 ms 1784 KB Output is correct
4 Correct 5 ms 1784 KB Output is correct
5 Correct 6 ms 1656 KB Output is correct
6 Correct 5 ms 1784 KB Output is correct
7 Correct 5 ms 1656 KB Output is correct
8 Correct 5 ms 1656 KB Output is correct
9 Correct 5 ms 1712 KB Output is correct
10 Correct 5 ms 1656 KB Output is correct

Subtask #2
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 20688 KB Output is correct
2 Correct 199 ms 25080 KB Output is correct
3 Correct 268 ms 31352 KB Output is correct
4 Correct 301 ms 23496 KB Output is correct
5 Correct 279 ms 23416 KB Output is correct
6 Correct 196 ms 25036 KB Output is correct
7 Correct 207 ms 24956 KB Output is correct
8 Correct 317 ms 23288 KB Output is correct
9 Correct 298 ms 23516 KB Output is correct
10 Correct 291 ms 23440 KB Output is correct

Subtask #3
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1656 KB Output is correct
2 Correct 5 ms 1784 KB Output is correct
3 Correct 5 ms 1784 KB Output is correct
4 Correct 5 ms 1784 KB Output is correct
5 Correct 6 ms 1656 KB Output is correct
6 Correct 5 ms 1784 KB Output is correct
7 Correct 5 ms 1656 KB Output is correct
8 Correct 5 ms 1656 KB Output is correct
9 Correct 5 ms 1712 KB Output is correct
10 Correct 195 ms 20688 KB Output is correct
11 Correct 199 ms 25080 KB Output is correct
12 Correct 268 ms 31352 KB Output is correct
13 Correct 301 ms 23496 KB Output is correct
14 Correct 279 ms 23416 KB Output is correct
15 Correct 196 ms 25036 KB Output is correct
16 Correct 207 ms 24956 KB Output is correct
17 Correct 317 ms 23288 KB Output is correct
18 Correct 298 ms 23516 KB Output is correct
19 Correct 291 ms 23440 KB Output is correct
20 Correct 397 ms 35472 KB Output is correct
21 Correct 376 ms 35448 KB Output is correct
22 Incorrect 347 ms 35492 KB Output isn't correct
23 Halted 0 ms 0 KB -