Submission #36426

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
36426	2017-12-09T02:45:12 Z	cheater2k	UFO (IZhO14_ufo)	C++14	100 / 100	1479 ms	259968 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;
long long *a[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 long long[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
	a[0] = new long long[m + 1];
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			a[i][j] = a[i-1][j] + a[i][j-1] - a[i-1][j-1] + a[i][j];
		}
	}
	for (int i = p; i <= n; ++i) {
		for (int j = p; j <= m; ++j) ans = max(ans, a[i][j] - a[i-p][j] - a[i][j-p] + a[i-p][j-p]);
	}
	printf("%lld\n", ans);
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	41268 KB	Output is correct
2	Correct	0 ms	41268 KB	Output is correct
3	Correct	0 ms	41400 KB	Output is correct
4	Correct	19 ms	41664 KB	Output is correct
5	Correct	136 ms	44112 KB	Output is correct
6	Correct	289 ms	60592 KB	Output is correct
7	Correct	403 ms	98268 KB	Output is correct
8	Correct	353 ms	98268 KB	Output is correct
9	Correct	709 ms	89336 KB	Output is correct
10	Correct	829 ms	98268 KB	Output is correct
11	Correct	636 ms	100376 KB	Output is correct
12	Correct	1029 ms	98268 KB	Output is correct
13	Correct	1056 ms	99016 KB	Output is correct
14	Correct	789 ms	100376 KB	Output is correct
15	Correct	963 ms	98268 KB	Output is correct
16	Correct	333 ms	100376 KB	Output is correct
17	Correct	1449 ms	99016 KB	Output is correct
18	Correct	323 ms	97432 KB	Output is correct
19	Correct	603 ms	116320 KB	Output is correct
20	Correct	1479 ms	259968 KB	Output is correct