oj.uz

Submission #131318

# Submission time Handle Problem Language Result Execution time Memory
131318 2019-07-17T04:13:09 Z aura02 None (KOI17_shell) C++14
0 / 100
 1077 ms 100368 KB 
#include<iostream>
#include<algorithm>
using namespace std;

long long N, arr[1600][1600], DP[1600][1600], S;

class SegmentTree {
private:
	long long MAX, tree[7000], lazy[7000];
public:
	void propagation(int now, int s, int e) {
		if (!lazy[now])
			return;
		tree[now] += (e - s + 1)*lazy[now];
		if (e != s) {
			lazy[now * 2] += lazy[now];
			lazy[now * 2 + 1] += lazy[now];
		}
		lazy[now] = 0;
	}
	void update(int now, int s, int e, int l, int r, long long v) {
		propagation(now, s, e);
		if (r < s || e < l)
			return;
		if (l <= s && e <= r) {
			tree[now] += (e - s + 1)*v;
			if (s != e) {
				lazy[now * 2] += v;
				lazy[now * 2 + 1] += v;
			}
			return;
		}
		int m = (s + e) / 2;
		update(now * 2, s, m, l, r, v);
		update(now * 2 + 1, m + 1, e, l, r, v);
		tree[now] = tree[now * 2] + tree[now * 2 + 1];
	}

	long long sum(int now, int s, int e, int l, int r) {
		propagation(now, s, e);
		if (r < s || e < l)
			return 0;
		if (l <= s && e <= r)
			return tree[now];
		int m = (s + e) / 2;
		return sum(now * 2, s, m, l, r) + sum(now * 2 + 1, m + 1, e, l, r);
	}
};

SegmentTree ST[1600];

int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> arr[i][j];
			DP[i][j] = max(DP[i - 1][j], DP[i][j - 1])+arr[i][j];
			ST[i].update(1, 1, N, j, j, DP[i][j]);
		}
		S += ST[i].sum(1, 1, N, 1, N);
	}
	cout << S << "\n";
	for (int i = 1; i <= N; i++) {
		S = 0;
		char c;
		int a, b, d;
		cin >> c >> a >> b;
		if (c == 'U')
			d =  1;
		if (c == 'D')
			d = -1;
		long long l = b, r = b;
		for(int j=a; j<=N; j++){
			while (r <= N) {
				if (DP[j][r] + d > DP[j - 1][r + 1])
					r++;
				else
					break;
			}
			while (l < r && j!=a) {
				if (DP[j][l - 1] >= DP[j-1][l])
					l++;
				else
					break;

			}
			if (l > N && r > N)
				break;
			ST[j].update(1, 1, N, l, min(N,r), d);
		}
		for (int j = 1; j <= N; j++)
			S += ST[j].sum(1, 1, N, 1, N);
		cout << S << "\n";
	}
}

Compilation message

shell.cpp: In function 'int main()':
shell.cpp:75:18: warning: 'd' may be used uninitialized in this function [-Wmaybe-uninitialized]
     if (DP[j][r] + d > DP[j - 1][r + 1])
         ~~~~~~~~~^~~

Subtask #1
0 / 12.0

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

Subtask #2
0 / 34.0

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

Subtask #3
0 / 54.0

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