Submission #523453

#	Time	Username	Problem	Language	Result	Execution time	Memory
523453		boykut	UFO (IZhO14_ufo)	C++14	100 / 100	694 ms	94640 KiB

ufo

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> a;
vector<vector<long long>> pref;
vector<int> vec;
int K;

struct segment_tree {
	int n;
	vector<int> t;
	segment_tree() {
	}
	segment_tree(size_t s) {
		n = 1;
		while (n < s) n <<= 1;
		t.assign(2 * n, 0);
	}
	void update(int k, int x) {
		k += n;
		t[k] += x;
		for (k /= 2; k >= 1; k /= 2) {
			t[k] = max(t[k << 1], t[k << 1 | 1]);
		}
	}
	int query(int l, int r) {
		l += n; r += n;
		int ans = INT_MIN;
		while (l <= r) {
			if (l % 2 == 1) ans = max(ans, t[l++]);
			if (r % 2 == 0) ans = max(ans, t[r--]);
			l >>= 1; r >>= 1;
		}
		return ans;
	}
	void gol(int y, int v, int vl, int vr) {
		if (t[v] < y) return;
		if ((int)vec.size() == K) return;
		if (vl == vr) {
			vec.push_back(vl - 1);
			return;
		}
		int vm = (vl + vr) >> 1;
		gol(y, v << 1, vl, vm);
		gol(y, v << 1 | 1, vm + 1, vr);
	}
	void gor(int y, int v, int vl, int vr) {
		if (t[v] < y) return;
		if ((int)vec.size() == K) return;
		if (vl == vr) {
			vec.push_back(vl - 1);
			return;
		}
		int vm = (vl + vr) >> 1;
		gor(y, v << 1 | 1, vm + 1, vr);
		gor(y, v << 1, vl, vm);
	}
	void gol(int y) {
		gol(y, 1, 1, n);
	}
	void gor(int y) {
		gor(y, 1, 1, n);
	}
	
};

vector<segment_tree> row, col;

int getmaxRow(int x, int l, int r) {
	return row[x].query(l, r);
};

int getmaxCol(int x, int l, int r) {
	return col[x].query(l, r);
};

void update(int i, int j) {
	row[i].update(j, -1);
	col[j].update(i, -1);
	a[i][j]--;
}

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

	int n, m, r, k, p;
	cin >> n >> m >> r >> k >> p;
	K = r;

	a = vector<vector<int>>(n, vector<int>(m));
	row = vector<segment_tree> (n);
	col = vector<segment_tree> (m);

	for (int i = 0; i < n; i++) {
		row[i] = segment_tree(m);
		for (int j = 0; j < m; j++) {
			cin >> a[i][j];
			row[i].update(j, a[i][j]);
		}
	}
	for (int j = 0; j < m; j++) {
		col[j] = segment_tree(n);
		for (int i = 0; i < n; i++) {
			col[j].update(i, a[i][j]);
		}
	}

	tuple<int, int, int> op[k];
	for (int Q = 0; Q < k; Q++) {
		char c; int x, y;
		cin >> c >> x >> y;
		op[Q] = {c, x, y};
	}

	for (int Q = 0; Q < k; Q++) {
		char c; int x, y;
		tie(c, x, y) = op[Q]; x--;
		vec.clear();

		if (c == 'N' || c == 'S') {
			if (c == 'N') col[x].gol(y);
			else col[x].gor(y);
			for (auto i : vec) {
				update(i, x);
			}
		} else {
			if (c == 'W') row[x].gol(y);
			else row[x].gor(y);
			for (auto i : vec) {
				update(x, i);
			}
		}
	}

	//cout << row[0].query(0, m-1) << '\n';

	pref = vector<vector<long long>>(n, vector<long long>(m));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			//cout << a[i][j] << ' ';
			pref[i][j] = a[i][j];
			pref[i][j] += (i ? pref[i-1][j] : 0);
			pref[i][j] += (j ? pref[i][j-1] : 0);
			pref[i][j] -= (i && j ? pref[i-1][j-1] : 0);
		}
		//cout << '\n';
	}

	auto get = [&](int a, int b, int c, int d) ->long long {
		long long s = pref[c][d];
		s -= (a ? pref[a-1][d] : 0);
		s -= (b ? pref[c][b-1] : 0);
		s += (a && b ? pref[a-1][b-1] : 0);
		return s;
	};

	long long ans = LLONG_MIN;
	for (int i = 0; i + p - 1 < n; i++) {
		for (int j = 0; j + p - 1 < m; j++) {
			ans = max(ans, get(i, j, i + p - 1, j + p - 1));
		}
	}
	cout << ans << '\n';

	return 0;
}

Compilation message (stderr)

ufo.cpp: In constructor 'segment_tree::segment_tree(size_t)':
ufo.cpp:17:12: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
   17 |   while (n < s) n <<= 1;
      |          ~~^~~

• Subtask 1: 100 / 100