답안 #500594

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
500594 2021-12-31T13:52:13 Z keta_tsimakuridze UFO (IZhO14_ufo) C++14
60 / 100
1363 ms 67508 KB
#include<bits/stdc++.h>
#define f first
#define s second
#define pii pair<int,int>
using namespace std;
const int N = 1e6 + 5, mod = 1e9 + 7; // !
int t, root[N][2], tree[N * 8], le[N * 8], ri[N * 8], idx;
void build(int u,int l,int r) {
	if(l == r) {
		return;
	}
	le[u] = ++idx;
	ri[u] = ++idx;
	int mid = (l + r) / 2;
	build(le[u], l, mid);
	build(ri[u], mid + 1, r);
}
void upd(int u,int ind,int l,int r,int val) {
	if(l > ind || r < ind) return;
	if(l == r) {
		tree[u] = val;
		return;
	}
	int mid = (l + r) / 2;
	upd(le[u], ind, l, mid, val); upd(ri[u], ind, mid + 1, r, val);
	tree[u] = max(tree[le[u]], tree[ri[u]]);
}
int getL(int u,int l,int r,int val) {
	if(l == r) {
		if(tree[u] < val) return l + 1;
		return l;
	}
	int mid = (l + r) / 2;
	if(tree[le[u]] >= val) return getL(le[u], l, mid, val);
	return getL(ri[u], mid + 1, r, val);
}
int getR(int u,int l,int r,int val) {
	if(l == r) {
		if(tree[u] < val) return l + 1;
		return l;
	}
	int mid = (l + r) / 2;
	if(tree[ri[u]] < val) return getL(le[u], l, mid, val);
	return getL(ri[u], mid + 1, r, val);
}
main(){
	int n, m, r, k, p;
	cin >> n >> m >> r >> k >> p;
	vector<long long> a[n + 5];
	for(int i = 1; i <= n; i++) {
		root[i][0] = ++idx;
		a[i].resize(m + 1);
		build(root[i][0], 1, m);
		for(int j = 1; j <= m; j++) {
			cin >> a[i][j];
			upd(root[i][0], j,  1, m, a[i][j]);
		}
	}
	for(int j = 1; j <= m; j++) {
		root[j][1] = ++idx;
		build(root[j][1], 1, n);
		for(int i = 1; i <= n; i++) {
			upd(root[j][1], i, 1, n, a[i][j]);
		}
	}
	while(k--) {
		char c;
		int i, h;
		cin >> c >> i >> h;
		if(c == 'W' || c == 'E') {
			int cnt = 0;
			while(true) {
				cnt++;
				if(cnt > r) break;
				int x;
				if(c == 'W') x = getL(root[i][0], 1, m, h);
				else x = getR(root[i][0],  1, m, h);
				if(x == m + 1) break;
				a[i][x]--;
				upd(root[i][0], x, 1, m, a[i][x]);
				upd(root[x][1], i, 1, n, a[i][x]);
			}
		}
		else {
			int cnt = 0; 
			while(true) {
				cnt++;
				if(cnt > r) break;
				int x;
				if(c == 'N') x = getL(root[i][1], 1, n, h);
				else x = getR(root[i][1], 1, n, h);
				
				if(x == n + 1) break;
				a[x][i] --;
				upd(root[i][1], x, 1, n, a[x][i]);
				upd(root[x][0], i, 1, m, a[x][i]);
				
			}
		}
	}
	long long ans = 0;
	a[0].resize(m + 1);
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
			if(i >= p && j >= p) ans = max(ans, a[i][j] + a[i - p][j - p] - a[i - p][j] - a[i][j - p]);
		}
	}
	cout << ans;

}

Compilation message

ufo.cpp:46:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   46 | main(){
      | ^~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 300 KB Output is correct
2 Incorrect 1 ms 296 KB Output isn't correct
3 Incorrect 2 ms 460 KB Output isn't correct
4 Incorrect 18 ms 948 KB Output isn't correct
5 Incorrect 114 ms 3736 KB Output isn't correct
6 Incorrect 332 ms 30484 KB Output isn't correct
7 Correct 773 ms 63416 KB Output is correct
8 Correct 632 ms 59852 KB Output is correct
9 Correct 867 ms 58868 KB Output is correct
10 Correct 842 ms 59160 KB Output is correct
11 Correct 775 ms 56436 KB Output is correct
12 Correct 858 ms 59084 KB Output is correct
13 Correct 1052 ms 62968 KB Output is correct
14 Correct 711 ms 56644 KB Output is correct
15 Incorrect 845 ms 60484 KB Output isn't correct
16 Correct 765 ms 58712 KB Output is correct
17 Incorrect 1363 ms 67508 KB Output isn't correct
18 Correct 752 ms 56980 KB Output is correct
19 Incorrect 893 ms 60984 KB Output isn't correct
20 Correct 1188 ms 55648 KB Output is correct