Submission #1134445

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134445		stdfloat	UFO (IZhO14_ufo)	C++20	100 / 100	1565 ms	74656 KiB

ufo

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

vector<vector<int>> st[2];

int upd(int tp, int x, int nd, int l, int r, int y, int vl) {
	if (r < y || y < l) return st[tp][x][nd];

	if (l == r) return st[tp][x][nd] += vl;

	int ch = (nd << 1) | 1, md = (l + r) >> 1;
	return st[tp][x][nd] = max(upd(tp, x, ch, l, md, y, vl), upd(tp, x, ch + 1, md + 1, r, y, vl));
}

int fnd(int tp, int x, int nd, int l, int r, int xl, int xr, int vl, bool tr) {
	if (r <= xl || xr <= l || st[tp][x][nd] < vl) return -1;

	if (l == r) return l;

	int ch = (nd << 1) | 1, md = (l + r) >> 1;

	int res;
	if (!tr) {
		res = fnd(tp, x, ch, l, md, xl, xr, vl, tr);
		if (!~res) res = fnd(tp, x, ch + 1, md + 1, r, xl, xr, vl, tr);
	}
	else {
		res = fnd(tp, x, ch + 1, md + 1, r, xl, xr, vl, tr);
		if (!~res) res = fnd(tp, x, ch, l, md, xl, xr, vl, tr);
	}

	return res;
}

int fnd2(int tp, int x, int nd, int l, int r, int y) {
	if (r < y || y < l) return 0;

	if (l == r) return st[tp][x][nd];

	int ch = (nd << 1) | 1, md = (l + r) >> 1;
	return max(fnd2(tp, x, ch, l, md, y), fnd2(tp, x, ch + 1, md + 1, r, y));
}

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);

	int n, m, R, K, P;
	cin >> n >> m >> R >> K >> P;

	vector<vector<int>> a(n, vector<int>(m));
	for (auto &i : a) {
		for (auto &j : i)
			cin >> j;
	}

	for (int i = 0; i < 2; i++)
		st[i].assign((!i ? n : m), vector<int>((!i ? m : n) << 2));

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			upd(0, i, 0, 0, m - 1, j, a[i][j]);
			upd(1, j, 0, 0, n - 1, i, a[i][j]);
		}
	}

	while (K--) {
		char c;
		int x, h;
		cin >> c >> x >> h; x--;

		int ls = -1, rs = INT_MAX;
		int tp = (c == 'W' ? 0 : c == 'E' ? 1 : 2 + (c == 'S')), r = (tp < 2 ? m : n) - 1;
		for (int z = 0; z < R; z++) {
			int ind = fnd(tp >> 1, x, 0, 0, r, ls, rs, h, tp & 1);

			if (ind == -1) break;

			if (!(tp & 1)) ls = ind;
			else rs = ind;

			int remx = x, remind = ind;

			if (1 < tp) swap(x, ind);

			upd(0, x, 0, 0, m - 1, ind, -1);
			upd(1, ind, 0, 0, n - 1, x, -1);
		
			x = remx; ind = remind;
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++)
			a[i][j] = fnd2(0, i, 0, 0, m - 1, j);
	}

	ll mx = 0;
	for (int i = 0; i + P <= n; i++) {
		for (int j = 0; j + P <= m; j++) {
			ll sm = 0;
			for (int x = i; x < i + P; x++) {
				for (int y = j; y < j + P; y++)
					sm += a[x][y];
			}

			mx = max(mx, sm);
		}
	}

	cout << mx;
}

• Subtask 1: 100 / 100