Submission #344734

#	Time	Username	Problem	Language	Result	Execution time	Memory
344734		_ani	UFO (IZhO14_ufo)	C++17	100 / 100	1940 ms	141180 KiB

ufo

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
const int inf = 1'000'000'000;
vector<vector<ll>> a;
vector<vector<ll>> tr, tc;
void Buildr(int v, int vl, int vr, int i) {//checked
	if (vl == vr) {
		tr[i][v] = a[i][vl];
		return;
	}
	int m = (vl + vr) / 2;
	Buildr(v * 2, vl, m, i);
	Buildr(v * 2 + 1, m + 1, vr, i);
	tr[i][v] = max(tr[i][v * 2], tr[i][v * 2 + 1]);
}
void Buildc(int v, int vl, int vr, int j) {//checked
	if (vl == vr) {
		tc[j][v] = a[vl][j];
		return;
	}
	int m = (vl + vr) / 2;
	Buildc(v * 2, vl, m, j);
	Buildc(v * 2 + 1, m + 1, vr, j);
	tc[j][v] = max(tc[j][v * 2], tc[j][v * 2 + 1]);
}
int RFirstGreater(int v, int vl, int vr, int l, int r, int i, ll k) {//checked
	if (vl == vr) {
		if (tr[i][v] >= k)return vl;
		return inf;
	}
	if (vl == l && vr == r) {
		if (tr[i][v] < k)return inf;
		if (tr[i][v * 2] >= k)
			return RFirstGreater(v * 2, vl, (vl + vr) / 2, vl, (vl + vr) / 2, i, k);
		return RFirstGreater(v * 2 + 1, (vl + vr) / 2 + 1, vr, (vl + vr) / 2 + 1, vr, i, k);
	}
	int m = (vl + vr) / 2;
	if (r <= m)return RFirstGreater(v * 2, vl, m, l, r, i, k);
	if (l > m)return RFirstGreater(v * 2 + 1, m + 1, vr, l, r, i, k);
	
	int res = inf;
	res = min(res, RFirstGreater(v * 2, vl, m, l, min(r, m), i, k));
	res = min(res, RFirstGreater(v * 2 + 1, m + 1, vr, max(l, m + 1), r, i, k));
	return res;
}
int RLastGreater(int v, int vl, int vr, int l, int r, int i, ll k) {//checked
	if (vl == vr) {
		if (tr[i][v] >= k)return vl;
		return -1;
	}
	if (vl == l && vr == r) {
		if (tr[i][v] < k)return -1;
		if (tr[i][v * 2 + 1] >= k)
			return RLastGreater(v * 2 + 1, (vl + vr) / 2 + 1, vr, (vl + vr) / 2 + 1, vr, i, k);
		return RLastGreater(v * 2, vl, (vl + vr) / 2, vl, (vl + vr) / 2, i, k);
	}
	int m = (vl + vr) / 2;
	if (r <= m)return RLastGreater(v * 2, vl, m, l, r, i, k);
	if (l > m)return RLastGreater(v * 2 + 1, m + 1, vr, l, r, i, k);

	int res = -1;
	res = max(res, RLastGreater(v * 2, vl, m, l, min(r, m), i, k));
	res = max(res, RLastGreater(v * 2 + 1, m + 1, vr, max(l, m + 1), r, i, k));
	return res;
}
int CFirstGreater(int v, int vl, int vr, int l, int r, int j, ll k) {//checked
	if (vl == vr) {
		if (tc[j][v] >= k)return vl;
		return inf;
	}
	if (vl == l && vr == r) {
		if (tc[j][v] < k)return inf;
		if (tc[j][v * 2] >= k)
			return CFirstGreater(v * 2, vl, (vl + vr) / 2, vl, (vl + vr) / 2, j, k);
		return CFirstGreater(v * 2 + 1, (vl + vr) / 2 + 1, vr, (vl + vr) / 2 + 1, vr, j, k);
	}
	int m = (vl + vr) / 2;
	if (r <= m)return CFirstGreater(v * 2, vl, m, l, r, j, k);
	if (l > m)return CFirstGreater(v * 2 + 1, m + 1, vr, l, r, j, k);

	int res = inf;
	res = min(res, CFirstGreater(v * 2, vl, m, l, min(r, m), j, k));
	res = min(res, CFirstGreater(v * 2 + 1, m + 1, vr, max(l, m + 1), r, j, k));
	return res;
}
int CLastGreater(int v, int vl, int vr, int l, int r, int j, ll k) {//checked
	if (vl == vr) {
		if (tc[j][v] >= k)return vl;
		return -1;
	}
	if (vl == l && vr == r) {
		if (tc[j][v] < k)return -1;
		if (tc[j][v * 2 + 1] >= k)
			return CLastGreater(v * 2 + 1, (vl + vr) / 2 + 1, vr, (vl + vr) / 2 + 1, vr, j, k);
		return CLastGreater(v * 2, vl, (vl + vr) / 2, vl, (vl + vr) / 2, j, k);
	}
	int m = (vl + vr) / 2;
	if (r <= m)return CLastGreater(v * 2, vl, m, l, r, j, k);
	if (l > m)return CLastGreater(v * 2 + 1, m + 1, vr, l, r, j, k);

	int res = -1;
	res = max(res, CLastGreater(v * 2, vl, m, l, min(r, m), j, k));
	res = max(res, CLastGreater(v * 2 + 1, m + 1, vr, max(l, m + 1), r, j, k));
	return res;
}
void RUpd(int v, int vl, int vr, int i, int j) {//checked
	if (vl == vr) {
		tr[i][v]--;
		return;
	}
	int m = (vl + vr) / 2;
	if (j <= m)
		RUpd(v * 2, vl, m, i, j);
	else
		RUpd(v * 2 + 1, m + 1, vr, i, j);
	tr[i][v] = max(tr[i][v * 2], tr[i][v * 2 + 1]);
}
void CUpd(int v, int vl, int vr, int i, int j) {//checked
	if (vl == vr) {
		tc[j][v]--;
		return;
	}
	int m = (vl + vr) / 2;
	if (i <= m)
		CUpd(v * 2, vl, m, i, j);
	else
		CUpd(v * 2 + 1, m + 1, vr, i, j);
	tc[j][v] = max(tc[j][v * 2], tc[j][v * 2 + 1]);
}
ll Get(int v, int vl, int vr, int i, int j) {//checked
	if (vl == vr)return tr[i][v];
	int m = (vl + vr) / 2;
	if (j <= m)return Get(v * 2, vl, m, i, j);
	return Get(v * 2 + 1, m + 1, vr, i, j);
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n, m, r, k, p;
	cin >> n >> m >> r >> k >> p;
	a.resize(n);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
		{
			ll x;
			cin >> x;
			a[i].push_back(x);
		}
	tr.resize(n);
	for (int i = 0; i < n; i++) {
		tr[i].resize(4 * m + 4);
		Buildr(1, 0, m - 1, i);
	}
	tc.resize(m);
	for (int j = 0; j < m; j++) {
		tc[j].resize(4 * n + 4);
		Buildc(1, 0, n - 1, j);
	}
	while (k--)
	{
		char s;
		int x;
		ll h;
		cin >> s >> x >> h;
		x--;
		int ind;
		if (s == 'W' || s == 'N')ind = -1;
		else ind = inf;
		for (int i = 0; i < r; i++) {
			if (s == 'W') {
				int cur = RFirstGreater(1, 0, m - 1, ind + 1, m - 1, x, h);
			//	cerr << "cur index " << cur << '\n';
				if (cur == inf) break;
				RUpd(1, 0, m - 1, x, cur);
				CUpd(1, 0, n - 1, x, cur);
				ind = cur;
				if (ind + 1 >= m)
					break;
			}
			if (s == 'N') {
				int cur = CFirstGreater(1, 0, n - 1, ind + 1, n - 1, x, h);
			//	cerr << "cur index " << cur << '\n';
				if (cur == inf) break;
				RUpd(1, 0, m - 1, cur, x);
				CUpd(1, 0, n - 1, cur, x);
				ind = cur;
				if (ind + 1 >= n)
					break;
			}
			if (s == 'E') {
				int cur = RLastGreater(1, 0, m - 1, 0, min(ind, m) - 1, x, h);
			//	cerr << "cur index " << cur << '\n';
				if (cur == -1) break;
				RUpd(1, 0, m - 1, x, cur);
				CUpd(1, 0, n - 1, x, cur);
				ind = cur;
				if (ind - 1 < 0)
					break;
			}
			if (s == 'S') {
				int cur = CLastGreater(1, 0, n - 1, 0, min(ind, n) - 1, x, h);
			//	cerr << "cur index " << cur << '\n';
				if (cur == -1) break;
				RUpd(1, 0, m - 1, cur, x);
				CUpd(1, 0, n - 1, cur, x);
				ind = cur;
				if (ind - 1 < 0)
					break;
			}
		}
	}
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			a[i][j] = Get(1, 0, m - 1, i, j);
	ll ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
	//		cerr << a[i][j] << ' ';
			if (i + p > n || j + p > m)continue;
			ll cur = 0;
			for (int x = i; x < i + p; x++)
				for (int y = j; y < j + p; y++)
					cur += a[x][y];
			ans = max(ans, cur);
		}
	//	cerr << '\n';
	}
	cout << ans << '\n';
	return 0;
}

• Subtask 1: 100 / 100