oj.uz

Submission #158465

# Submission time Handle Problem Language Result Execution time Memory
158465 2019-10-17T08:50:37 Z maruii None (KOI17_shell) C++14
0 / 100
 201 ms 31292 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];

void up(int x, int y, int c) {
	while (1) {
		if (c > 0) while (y + 1 <= N && fen[x].query(y + 1) == fen[x].query(y) + A[x][y + 1]) y++;
		else while (y + 1 <= N && fen[x].query(y + 1) != fen[x - 1].query(y + 1) + A[x][y + 1]) y++;
		ye[x] = y;
		if (x == N || (c > 0 && fen[x + 1].query(y) != fen[x].query(y) + A[x + 1][y]) || (c < 0 && fen[x + 1].query(y) != fen[x + 1].query(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 && fen[x + 1].query(y) == fen[x].query(y) + A[x + 1][y]) ys[++x] = y;
		else while (x + 1 <= N && fen[x + 1].query(y) != fen[x + 1].query(y - 1) + A[x + 1][y]) ys[++x] = y;
		if (y == N || (c > 0 && fen[x].query(y + 1) != fen[x].query(y) + A[x][y + 1]) || (c < 0 && fen[x].query(y + 1) != fen[x - 1].query(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]);
		fen[i].update(j, j, f[i][j]);
		cost += f[i][j];
	}
	for (int i = 1; i <= N; ++i) {
		fen[i].update(0, 0, -1);
		fen[0].update(i, i, -1);
	}

	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 1784 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 201 ms 31292 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 1784 KB Output isn't correct
2 Halted 0 ms 0 KB -