Submission #523450

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
523450	2022-02-07T16:28:49 Z	boykut	UFO (IZhO14_ufo)	C++14	85 / 100	2000 ms	78592 KB

ufo

#include <bits/stdc++.h>

using namespace std;

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

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 += 1 + 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 += 1 + n; r += 1 + 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;
	}
};

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;

	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];
		int cnt = r;
		x--;

		if (c == 'W') {
			int start = 0;
			while (cnt > 0 && start < m) {
				int l = start, r = m - 1;
				while (l < r) {
					int m = (l + r) >> 1;
					if (getmaxRow(x, start, m) >= y)
						r = m;
					else
						l = m + 1;
				}
				if (getmaxRow(x, start, r) >= y) {
					update(x, r);
					cnt--;
					start = r + 1;
				} else break;
			}
		} else if (c == 'E') {
			int start = m - 1;
			while (cnt > 0 && start >= 0) {
				int l = 0, r = start;
				while (l < r) {
					int m = (l + r + 1) >> 1;
					if (getmaxRow(x, m, start) >= y)
						l = m;
					else
						r = m - 1;
				}
				if (getmaxRow(x, l, start) >= y) {
					update(x, l);
					cnt--;
					start = l - 1;
				} else break;
			}
		} else if (c == 'N') {
			int start = 0;
			while (cnt > 0 && start < n) {
				int l = start, r = n - 1;
				while (l < r) {
					int m = (l + r) >> 1;
					if (getmaxCol(x, start, m) >= y)
						r = m;
					else
						l = m + 1;
				}
				if (getmaxCol(x, start, r) >= y) {
					update(r, x);
					cnt--;
					start = r + 1;
				} else break;
			}
		} else {
			int start = n - 1;
			while (cnt > 0 && start >= 0) {
				int l = 0, r = start;
				while (l < r) {
					int m = (l + r + 1) >> 1;
					if (getmaxCol(x, m, start) >= y)
						l = m;
					else
						r = m - 1;
				}
				if (getmaxCol(x, l, start) >= y) {
					update(l, x);
					cnt--;
					start = l - 1;
				} else break;
			}
		}
	}

	//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:15:12: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
   15 |   while (n < s) n <<= 1;
      |          ~~^~~

Subtask #1

85.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	17 ms	680 KB	Output is correct
5	Correct	97 ms	2968 KB	Output is correct
6	Correct	196 ms	17920 KB	Output is correct
7	Correct	409 ms	42684 KB	Output is correct
8	Correct	329 ms	42676 KB	Output is correct
9	Correct	1002 ms	39988 KB	Output is correct
10	Correct	1506 ms	42680 KB	Output is correct
11	Correct	1027 ms	36376 KB	Output is correct
12	Correct	1613 ms	42680 KB	Output is correct
13	Correct	1784 ms	50168 KB	Output is correct
14	Correct	1302 ms	36280 KB	Output is correct
15	Execution timed out	2083 ms	33996 KB	Time limit exceeded
16	Correct	371 ms	37444 KB	Output is correct
17	Execution timed out	2087 ms	38392 KB	Time limit exceeded
18	Correct	360 ms	42920 KB	Output is correct
19	Correct	868 ms	49060 KB	Output is correct
20	Execution timed out	2087 ms	78592 KB	Time limit exceeded