Submission #36426

#	Time	Username	Problem	Language	Result	Execution time	Memory
36426		cheater2k	UFO (IZhO14_ufo)	C++14	100 / 100	1479 ms	259968 KiB

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 / 100