oj.uz

Submission #480096

# Submission time Handle Problem Language Result Execution time Memory
480096 2021-10-14T14:54:38 Z 1bin None (KOI17_shell) C++14
100 / 100
 1525 ms 92572 KB 
#include <bits/stdc++.h>

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 1505;
int n, k, base = 1, x, y, l, r;
ll  dp[NMAX][NMAX], a[NMAX][NMAX], p ,ans;
vector<ll> seg[NMAX];
char c;

void update(int y, int idx, ll v) {
	idx += base;
	while (idx) {
		seg[y][idx] += v;
		idx /= 2;
	}
	return;
}

ll find(int y, int l, int r) {
	ll ret = dp[y][r];
	l += base; r += base;
	while (l <= r) {
		if (l & 1) ret += seg[y][l++];
		if (!(r & 1)) ret += seg[y][r--];
		l /= 2; r /= 2;
	}
	return ret;
}

int main(void) {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> n;
	while (base < n + 2) base *= 2;
	for (int i = 0; i <= n; i++) seg[i].resize(base * 2);

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) cin >> a[i][j];
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) {
			dp[i][j] = max(dp[i][j], dp[i - 1][j]);
			dp[i][j] = max(dp[i][j], dp[i][j - 1]);
			dp[i][j] += a[i][j];
			ans += dp[i][j];
		}

	cout << ans << '\n';
	for (int t = 0; t < n; t++) {
		cin >> c >> y >> x;
		l = r = x;
		(c == 'U') ? p = 1 : p = -1;
		a[y][x] += p;
		for (int i = y; i <= n; i++) {
			if (i != y) {
				for (; l <= r; l++) {
					ll b = find(i, 0, l);
					ll now = max(find(i, 0, l - 1), find(i - 1, 0, l)) + a[i][l];
					if (b != now) break;
				}
			}
			if (l > r) break;
			update(i, l, p);
			for (; r + 1 <= n; r++) {
				ll b = find(i, 0, r + 1) - p;
				ll now = max(find(i, 0, r), find(i - 1, 0, r + 1)) + a[i][r + 1];
				if (now == b) break;
			}
			update(i, r + 1, -p);
			//cout << "L : " << l << "   R : " << r << '\n';
			ans += p * (r - l + 1);
		}
		cout << ans << '\n';
	}
	return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1464 KB Output is correct
2 Correct 2 ms 1484 KB Output is correct
3 Correct 3 ms 1484 KB Output is correct
4 Correct 3 ms 1544 KB Output is correct
5 Correct 4 ms 1484 KB Output is correct
6 Correct 4 ms 1484 KB Output is correct
7 Correct 3 ms 1476 KB Output is correct
8 Correct 2 ms 1484 KB Output is correct
9 Correct 3 ms 1508 KB Output is correct
10 Correct 2 ms 1484 KB Output is correct

Subtask #2
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 83840 KB Output is correct
2 Correct 190 ms 83856 KB Output is correct
3 Correct 193 ms 83848 KB Output is correct
4 Correct 165 ms 83860 KB Output is correct
5 Correct 160 ms 83828 KB Output is correct
6 Correct 179 ms 83744 KB Output is correct
7 Correct 189 ms 83760 KB Output is correct
8 Correct 204 ms 83860 KB Output is correct
9 Correct 176 ms 83732 KB Output is correct
10 Correct 175 ms 83788 KB Output is correct

Subtask #3
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1464 KB Output is correct
2 Correct 2 ms 1484 KB Output is correct
3 Correct 3 ms 1484 KB Output is correct
4 Correct 3 ms 1544 KB Output is correct
5 Correct 4 ms 1484 KB Output is correct
6 Correct 4 ms 1484 KB Output is correct
7 Correct 3 ms 1476 KB Output is correct
8 Correct 2 ms 1484 KB Output is correct
9 Correct 3 ms 1508 KB Output is correct
10 Correct 217 ms 83840 KB Output is correct
11 Correct 190 ms 83856 KB Output is correct
12 Correct 193 ms 83848 KB Output is correct
13 Correct 165 ms 83860 KB Output is correct
14 Correct 160 ms 83828 KB Output is correct
15 Correct 179 ms 83744 KB Output is correct
16 Correct 189 ms 83760 KB Output is correct
17 Correct 204 ms 83860 KB Output is correct
18 Correct 176 ms 83732 KB Output is correct
19 Correct 175 ms 83788 KB Output is correct
20 Correct 2 ms 1484 KB Output is correct
21 Correct 261 ms 83848 KB Output is correct
22 Correct 269 ms 92372 KB Output is correct
23 Correct 227 ms 92432 KB Output is correct
24 Correct 1525 ms 92448 KB Output is correct
25 Correct 1400 ms 92484 KB Output is correct
26 Correct 1328 ms 92392 KB Output is correct
27 Correct 192 ms 88260 KB Output is correct
28 Correct 200 ms 88416 KB Output is correct
29 Correct 230 ms 92404 KB Output is correct
30 Correct 234 ms 92324 KB Output is correct
31 Correct 1442 ms 92572 KB Output is correct
32 Correct 1476 ms 92452 KB Output is correct
33 Correct 194 ms 88288 KB Output is correct
34 Correct 170 ms 88228 KB Output is correct