oj.uz

Submission #158476

# Submission time Handle Problem Language Result Execution time Memory
158476 2019-10-17T09:25:20 Z maruii None (KOI17_shell) C++14
46 / 100
 399 ms 35836 KB 
#include <bits/stdc++.h>
using namespace std;

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

struct BIT {
	long long 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++;
		long long 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];
	}

	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 1740 KB Output is correct
3 Correct 5 ms 1784 KB Output is correct
4 Correct 6 ms 1784 KB Output is correct
5 Correct 6 ms 1784 KB Output is correct
6 Correct 5 ms 1528 KB Output is correct
7 Correct 6 ms 1656 KB Output is correct
8 Correct 5 ms 1784 KB Output is correct
9 Correct 6 ms 1656 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 198 ms 21368 KB Output is correct
2 Correct 196 ms 21312 KB Output is correct
3 Correct 399 ms 30584 KB Output is correct
4 Correct 332 ms 19252 KB Output is correct
5 Correct 313 ms 19192 KB Output is correct
6 Correct 204 ms 21340 KB Output is correct
7 Correct 196 ms 21244 KB Output is correct
8 Correct 324 ms 19096 KB Output is correct
9 Correct 308 ms 19276 KB Output is correct
10 Correct 293 ms 19192 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 1740 KB Output is correct
3 Correct 5 ms 1784 KB Output is correct
4 Correct 6 ms 1784 KB Output is correct
5 Correct 6 ms 1784 KB Output is correct
6 Correct 5 ms 1528 KB Output is correct
7 Correct 6 ms 1656 KB Output is correct
8 Correct 5 ms 1784 KB Output is correct
9 Correct 6 ms 1656 KB Output is correct
10 Correct 198 ms 21368 KB Output is correct
11 Correct 196 ms 21312 KB Output is correct
12 Correct 399 ms 30584 KB Output is correct
13 Correct 332 ms 19252 KB Output is correct
14 Correct 313 ms 19192 KB Output is correct
15 Correct 204 ms 21340 KB Output is correct
16 Correct 196 ms 21244 KB Output is correct
17 Correct 324 ms 19096 KB Output is correct
18 Correct 308 ms 19276 KB Output is correct
19 Correct 293 ms 19192 KB Output is correct
20 Correct 349 ms 35836 KB Output is correct
21 Correct 350 ms 35644 KB Output is correct
22 Incorrect 348 ms 35704 KB Output isn't correct
23 Halted 0 ms 0 KB -