답안 #523446

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
523446 2022-02-07T16:22:21 Z boykut UFO (IZhO14_ufo) C++14
0 / 100
2000 ms 78556 KB
#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);
	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;
      |          ~~^~~
# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Incorrect 2 ms 332 KB Output isn't correct
4 Incorrect 17 ms 708 KB Output isn't correct
5 Incorrect 97 ms 3228 KB Output isn't correct
6 Incorrect 226 ms 20720 KB Output isn't correct
7 Incorrect 498 ms 47656 KB Output isn't correct
8 Incorrect 402 ms 44076 KB Output isn't correct
9 Incorrect 1109 ms 41720 KB Output isn't correct
10 Incorrect 1602 ms 43992 KB Output isn't correct
11 Incorrect 1098 ms 37280 KB Output isn't correct
12 Incorrect 1823 ms 44004 KB Output isn't correct
13 Incorrect 1942 ms 52228 KB Output isn't correct
14 Incorrect 1399 ms 37280 KB Output isn't correct
15 Execution timed out 2090 ms 33980 KB Time limit exceeded
16 Incorrect 449 ms 38592 KB Output isn't correct
17 Execution timed out 2035 ms 38280 KB Time limit exceeded
18 Incorrect 423 ms 44800 KB Output isn't correct
19 Incorrect 953 ms 49536 KB Output isn't correct
20 Execution timed out 2087 ms 78556 KB Time limit exceeded