Submission #523453

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
523453	2022-02-07T16:36:35 Z	boykut	UFO (IZhO14_ufo)	C++14	100 / 100	694 ms	94640 KB

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

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	10 ms	876 KB	Output is correct
5	Correct	44 ms	3368 KB	Output is correct
6	Correct	123 ms	18360 KB	Output is correct
7	Correct	206 ms	43012 KB	Output is correct
8	Correct	197 ms	43124 KB	Output is correct
9	Correct	263 ms	40456 KB	Output is correct
10	Correct	331 ms	43012 KB	Output is correct
11	Correct	221 ms	36660 KB	Output is correct
12	Correct	334 ms	43056 KB	Output is correct
13	Correct	373 ms	50456 KB	Output is correct
14	Correct	302 ms	36676 KB	Output is correct
15	Correct	361 ms	43104 KB	Output is correct
16	Correct	183 ms	37808 KB	Output is correct
17	Correct	539 ms	50816 KB	Output is correct
18	Correct	172 ms	43264 KB	Output is correct
19	Correct	238 ms	49488 KB	Output is correct
20	Correct	694 ms	94640 KB	Output is correct