답안 #523419

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
523419 2022-02-07T15:44:42 Z boykut UFO (IZhO14_ufo) C++14
50 / 100
2000 ms 77728 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 i, int x, int v, int vl, int vr) {
		if (vl == vr) {
			t[v] += x;
		} else {
			int vm = vl + vr >> 1;
			if (i <= vm)
				update(i, x, v << 1, vl, vm);
			else
				update(i, x, v << 1 | 1, vm + 1, vr);
			t[v] = max(t[v << 1], t[v << 1 | 1]);
		}
	}
	void update(int i, int x) {
		update(i, x, 1, 0, n - 1);
	}
	int query(int l, int r, int v, int vl, int vr) {
		if (l > vr || vl > r) return INT_MIN;
		if (l <= vl && vr <= r) return t[v];
		int vm = vl + vr >> 1;
		int q1 = query(l, r, v << 1, vl, vm);
		int q2 = query(l, r, v << 1 | 1, vm + 1, vr);
		return max(q1, q2);
	}
	int query(int l, int r) {
		return query(l, r, 1, 0, n - 1);
	}
};

vector<segment_tree> row, col;

int getmaxRow(int x, int l, int r) {
	//int ans = INT_MIN;
	//for (int j = l; j <= r; j++) ans = max(ans, a[x][j]);
	return row[x].query(l, r);
};

int getmaxCol(int x, int l, int r) {
	// int ans = INT_MIN;
	// for (int j = l; j <= r; j++) ans = max(ans, a[j][x]);
	return col[x].query(l, r);
};

void updateRow(int x, int j) {
	//a[x][j]--;
	row[x].update(j, -1);
	col[j].update(x, -1);
}
void updateCol(int x, int j) {
	//a[j][x]--;
	col[x].update(j, -1);
	row[j].update(x, -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]);
		}
	}

	while (k--) {
		char c; cin >> c;
		int x, y; cin >> x >> y;
		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) / 2;
					if (getmaxRow(x, start, m) >= y)
						r = m;
					else
						l = m + 1;
				}
				if (getmaxRow(x, start, r) >= y) {
					updateRow(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) / 2;
					if (getmaxRow(x, m, start) >= y)
						l = m;
					else
						r = m - 1;
				}
				if (getmaxRow(x, l, start) >= y) {
					updateRow(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) / 2;
					if (getmaxCol(x, start, m) >= y)
						r = m;
					else
						l = m + 1;
				}
				if (getmaxCol(x, start, r) >= y) {
					updateCol(x, r);
					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) / 2;
					if (getmaxCol(x, m, start) >= y)
						l = m;
					else
						r = m - 1;
				}
				if (getmaxCol(x, l, start) >= y) {
					updateCol(x, l);
					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;
      |          ~~^~~
ufo.cpp: In member function 'void segment_tree::update(int, int, int, int, int)':
ufo.cpp:22:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |    int vm = vl + vr >> 1;
      |             ~~~^~~~
ufo.cpp: In member function 'int segment_tree::query(int, int, int, int, int)':
ufo.cpp:36:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |   int vm = vl + vr >> 1;
      |            ~~~^~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 308 KB Output is correct
3 Correct 2 ms 328 KB Output is correct
4 Correct 48 ms 672 KB Output is correct
5 Correct 387 ms 3012 KB Output is correct
6 Correct 525 ms 20632 KB Output is correct
7 Correct 759 ms 48212 KB Output is correct
8 Correct 686 ms 44872 KB Output is correct
9 Execution timed out 2054 ms 32384 KB Time limit exceeded
10 Execution timed out 2055 ms 34676 KB Time limit exceeded
11 Execution timed out 2086 ms 28160 KB Time limit exceeded
12 Execution timed out 2058 ms 34628 KB Time limit exceeded
13 Execution timed out 2011 ms 38180 KB Time limit exceeded
14 Execution timed out 2052 ms 28272 KB Time limit exceeded
15 Execution timed out 2081 ms 35716 KB Time limit exceeded
16 Correct 818 ms 39404 KB Output is correct
17 Execution timed out 2009 ms 41848 KB Time limit exceeded
18 Correct 718 ms 44860 KB Output is correct
19 Execution timed out 2068 ms 41560 KB Time limit exceeded
20 Execution timed out 2061 ms 77728 KB Time limit exceeded