Submission #36425

# Submission time Handle Problem Language Result Execution time Memory
36425 2017-12-09T02:42:43 Z cheater2k UFO (IZhO14_ufo) C++14
95 / 100
1466 ms 262144 KB
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5;

struct SegmentTree {
	int *T;
	int sz;
	void init(int _sz=0) {
		sz = _sz;
		T = new int[4 * (sz + 10)]; 
	}

	#define mid ((l + r) >> 1)
	void upd(int v, int l, int r, int pos, int val) {
		if (l > r || l > pos || r < pos) return;
		if (l == r) { T[v] = val; return; }
		upd(v << 1, l, mid, pos, val); upd(v << 1 | 1, mid + 1, r, pos, val);
		T[v] = max(T[v << 1], T[v << 1 | 1]);
	}

	int getL(int v, int l, int r, int L, int val) { // [L,sz]
		// find the smallest i such as i >= L and a[i] >= val
		if (r < L || l > r) return sz + 1;
		if (T[v] < val) return sz + 1;
		if (l == r) {
			if (T[v] >= val) return l; else return sz + 1;
		}
		int lef = getL(v << 1, l, mid, L, val);
		if (lef < sz + 1) return lef;
		else return getL(v << 1 | 1, mid + 1, r, L, val);
	}

	int getR(int v, int l, int r, int R, int val) { // [1,R]
		// find the greatest i such as i <= R and a[i] >= val
		if (l > R || l > r) return 0;
		if (T[v] < val) return 0;
		if (l == r) {
			if (T[v] >= val) return l; else return 0;
		}
		int rig = getR(v << 1 | 1, mid + 1, r, R, val);
		if (rig > 0) return rig;
		else return getR(v << 1, l, mid, R, val);
	}
	#undef mid

	void upd(int pos, int val) { upd(1, 1, sz, pos, val); }
	int getL(int pos, int val) { return getL(1, 1, sz, pos, val); }
	int getR(int pos, int val) { return getR(1, 1, sz, pos, val); }
} row[N], col[N];

int n, m, R, k, p;
int *a[N];
long long *sum[N];
long long ans;

void change(int r, int c) {
	a[r][c]--;
	row[r].upd(c, a[r][c]);
	col[c].upd(r, a[r][c]);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m >> R >> k >> p;
	for (int i = 1; i <= n; ++i) {
		a[i] = new int[m + 1];
		for (int j = 1; j <= m; ++j) cin >> a[i][j];
	}
	for (int i = 1; i <= n; ++i) {
		row[i].init(m);
	}
	for (int i = 1; i <= m; ++i) {
		col[i].init(n);
	}
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			row[i].upd(j, a[i][j]);
			col[j].upd(i, a[i][j]);
		}
	}
	
	// process queries
	while(k--) {
		char dir; int x, height; 
		cin >> dir >> x >> height;
		if (dir == 'W') {
			// row, getL
			int pos = 1, cnt = R;
			while(cnt > 0 && pos <= m) {
				pos = row[x].getL(pos, height); // [pos...m], >= height
				if (pos == m + 1) break;
				change(x, pos);
				--cnt; ++pos;
			}
		} else if (dir == 'E') {
			// row, getR
			int pos = m, cnt = R;
			while(cnt > 0 && pos >= 1) {
				pos = row[x].getR(pos, height); // [1...pos], >= height
				if (pos == 0) break;
				change(x, pos);
				--cnt; --pos; 
			}
		} else if (dir == 'N') {
			// col, getL
			int pos = 1, cnt = R;
			while(cnt > 0 && pos <= n) {
				pos = col[x].getL(pos, height); // [pos...n], >= height
				if (pos == n + 1) break;
				change(pos, x);
				--cnt; ++pos;
			}
		} else { // dir == 'S'
			// col, getR
			int pos = n, cnt = R;
			while(cnt > 0 && pos >= 1) {
				pos = col[x].getR(pos, height); // [1...pos], >= height
				if (pos == 0) break;
				change(pos, x);
				--cnt; --pos; 
			}
		}
	}

	// calculate sum
	sum[0] = new long long[m + 1];
	for (int i = 1; i <= n; ++i) {
		sum[i] = new long long[m + 1];
		for (int j = 1; j <= m; ++j) {
			sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + a[i][j];
		}
	}
	for (int i = p; i <= n; ++i) {
		for (int j = p; j <= m; ++j) ans = max(ans, sum[i][j] - sum[i-p][j] - sum[i][j-p] + sum[i-p][j-p]);
	}
	printf("%lld\n", ans);
}
# Verdict Execution time Memory Grader output
1 Correct 0 ms 49084 KB Output is correct
2 Correct 0 ms 49084 KB Output is correct
3 Correct 0 ms 49216 KB Output is correct
4 Correct 16 ms 49480 KB Output is correct
5 Correct 116 ms 52048 KB Output is correct
6 Correct 316 ms 70380 KB Output is correct
7 Correct 419 ms 110004 KB Output is correct
8 Correct 369 ms 110004 KB Output is correct
9 Correct 819 ms 101072 KB Output is correct
10 Correct 886 ms 110004 KB Output is correct
11 Correct 663 ms 111968 KB Output is correct
12 Correct 926 ms 110004 KB Output is correct
13 Correct 979 ms 113168 KB Output is correct
14 Correct 793 ms 111968 KB Output is correct
15 Correct 973 ms 110004 KB Output is correct
16 Correct 369 ms 111968 KB Output is correct
17 Correct 1409 ms 113168 KB Output is correct
18 Correct 309 ms 110924 KB Output is correct
19 Correct 503 ms 128056 KB Output is correct
20 Memory limit exceeded 1466 ms 262144 KB Memory limit exceeded