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

ufo

#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);
}

Subtask #1

95.0 / 100.0

#	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