Submission #523445

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
523445	2022-02-07T16:20:13 Z	boykut	UFO (IZhO14_ufo)	C++14	85 / 100	2000 ms	78564 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 += 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;
	}
};

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);
}

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++) {
			a[i][j] = row[i].query(j, 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	1 ms	204 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	14 ms	716 KB	Output is correct
5	Correct	102 ms	2976 KB	Output is correct
6	Correct	266 ms	17944 KB	Output is correct
7	Correct	365 ms	42712 KB	Output is correct
8	Correct	338 ms	42728 KB	Output is correct
9	Correct	998 ms	40120 KB	Output is correct
10	Correct	1509 ms	42684 KB	Output is correct
11	Correct	1040 ms	36272 KB	Output is correct
12	Correct	1733 ms	42676 KB	Output is correct
13	Correct	1892 ms	50040 KB	Output is correct
14	Correct	1510 ms	36280 KB	Output is correct
15	Execution timed out	2063 ms	34108 KB	Time limit exceeded
16	Correct	383 ms	37388 KB	Output is correct
17	Execution timed out	2076 ms	38416 KB	Time limit exceeded
18	Correct	357 ms	42948 KB	Output is correct
19	Correct	814 ms	49044 KB	Output is correct
20	Execution timed out	2077 ms	78564 KB	Time limit exceeded