oj.uz

Submission #158469

# Submission time Handle Problem Language Result Execution time Memory
158469 2019-10-17T09:03:56 Z maruii None (KOI17_shell) C++14
0 / 100
 165 ms 20208 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) {
	while (1) {
		if (c > 0) while (y + 1 <= N && query(x, y + 1) == query(x, y) + A[x][y + 1]) y++;
		else while (y + 1 <= N && query(x, y + 1) != query(x - 1, y + 1) + A[x][y + 1]) y++;
		ye[x] = y;
		if (x == N || (c > 0 && query(x + 1, y) != query(x, y) + A[x + 1][y]) || (c < 0 && query(x + 1, y) != query(x + 1, 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 && query(x + 1, y) == query(x, y) + A[x + 1][y]) ys[++x] = y;
		else while (x + 1 <= N && query(x + 1, y) != query(x + 1, y - 1) + A[x + 1][y]) ys[++x] = y;
		if (y == N || (c > 0 && query(x, y + 1) != query(x, y) + A[x][y + 1]) || (c < 0 && query(x, y + 1) != query(x - 1, 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]);
		cost += f[i][j];
	}
	for (int i = 1; i <= N; ++i) f[0][i] = f[i][0] = -1e9;

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

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1656 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 165 ms 20208 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 54.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1656 KB Output isn't correct
2 Halted 0 ms 0 KB -