Submission #36424

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
36424	2017-12-09T02:38:36 Z	cheater2k	UFO (IZhO14_ufo)	C++14	90 / 100	1566 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 = m, 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

90.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	19 ms	49480 KB	Output is correct
5	Correct	119 ms	52048 KB	Output is correct
6	Correct	333 ms	70380 KB	Output is correct
7	Correct	449 ms	110004 KB	Output is correct
8	Correct	329 ms	110004 KB	Output is correct
9	Correct	769 ms	101072 KB	Output is correct
10	Correct	953 ms	110004 KB	Output is correct
11	Correct	629 ms	111968 KB	Output is correct
12	Correct	916 ms	110004 KB	Output is correct
13	Correct	726 ms	113168 KB	Output is correct
14	Correct	799 ms	111968 KB	Output is correct
15	Correct	919 ms	110004 KB	Output is correct
16	Correct	369 ms	111968 KB	Output is correct
17	Incorrect	926 ms	113168 KB	Output isn't correct
18	Correct	333 ms	110924 KB	Output is correct
19	Correct	533 ms	128056 KB	Output is correct
20	Memory limit exceeded	1566 ms	262144 KB	Memory limit exceeded