답안 #338249

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
338249 2020-12-22T20:03:30 Z Tosic UFO (IZhO14_ufo) C++14
10 / 100
572 ms 262148 KB
#include <bits/stdc++.h>
#define maxn 1000010
using namespace std;

int n, m, r, k, p;
vector<vector<int> > a, c;
vector<int> rv;

struct segtree
{
	vector<int> tree;
	vector<int> resIdx;
	vector<int> a;
	int n, glR;
	segtree(){
		n=0;
		glR = 0;
	}
	void init(int sz, vector<int> tmp){
		n = sz;
		tree.resize(2*n+10, 0);
		a = tmp;
		init(0, 0, n-1);
	}
	void kidsO(int idx){
		tree[idx] = max(tree[idx*2+1], tree[idx*2+2]);
	}
	void init(int idx, int l, int r){
		if(l == r){
			tree[idx] = a[l];
			return;
		}
		int mid = (l+r)/2;
		init(idx*2+1, l ,mid);
		init(idx*2+2, mid+1, r);
		kidsO(idx);
	}
	void getF(int idx, int l, int r, int x){
		// first index so a[l] >= x
		if(tree[idx] < x){
			return;
		}
		if(l == r){
			--glR;//cerr << x << ' ' << tree[idx] << ' '<< l << '\n';
			resIdx.push_back(l);
			return;
		}
		int mid = (l+r)/2;
		if(tree[1+2*idx] >= x){
			getF(idx*2+1, l, mid, x);

		}if(glR){
				getF(idx*2+2, mid+1, r, x);
			}
			return;
		return;
	}
	void getL(int idx, int l, int r, int x){
		// lst index so a[l] >= x
		if(tree[idx] < x){
			return;
		}
		if(l == r){
			//cerr << glR << '\n';
			--glR;
			resIdx.push_back(l);
			return;
		}
		int mid = (l+r)/2;
		if(tree[2+2*idx] >= x){
			getL(idx*2+2, mid+1, r, x);
		}
		if(glR){
			getL(2*idx+1, l, mid, x);
		}
	}
	void upd(int idx, int l, int r, int x, int newV){
		if(l == r){
			a[l] += newV;
			tree[idx] += newV;
			return;
		}
		int mid = (l+r)/2;
		if(x<=mid){
			upd(2*idx+1, l, mid, x, newV);
		}
		if(x > mid){
			upd(2*(idx+1), mid+1, r, x, newV);
		}
		kidsO(idx);
	}
	int query(int idx, int l, int r, int qL, int qR){
		if(l > qR or r < qL){
			return 0;
		}
		if(l >=qL and r <= qR){
			return tree[idx];
		}
		int mid = (l+r)/2;
		return max(query(idx*2+1, l, mid, qL, qR), query(idx*2+2, mid+1, r, qL, qR));
	}
};

segtree rTrees[maxn], cTrees[maxn];

int tmpS(int x, int y){
	if(x < 0 or y < 0){
		return 0;
	}
	return c[x][y];
}

int getMax(){
	for(int i = 0; i < m; ++i){
		c[0][i] = a[0][i];
		if(i){
			c[0][i] += c[0][i-1];
		}
	}
	for(int i = 0; i < n; ++i){
		c[i][0] = a[i][0];
		if(i){
			c[i][0] += c[i-1][0];
		}
	}
	for(int i = 1; i < n; ++i){
		for(int j = 1; j < m; ++j){
			c[i][j] = a[i][j]+c[i-1][j]+c[i][j-1]-c[i-1][j-1];
		}
	}
	int res = 0;
	for(int i = 0; i < n-p+1; ++i){
		for(int j = 0; j < m-p+1; ++j){
			res = max(tmpS(i+p-1, j+p-1) - tmpS(i+p-1, j-1) - tmpS(i-1, j+p-1) + tmpS(i-1, j-1), res);
		}
	}
	return res;
}

int main(){
	ios_base::sync_with_stdio(0);
	cout.tie(0);
	cin.tie(0);
	cin >> n >> m >> r >> k >> p;
	a.resize(n, vector<int>(m));
	c.resize(n, vector<int>(m));
	rv.resize(m, 0);
	for(int i = 0; i < n; ++i){
		for(int j = 0; j < m; ++j){
			cin >> a[i][j];
		}
		rTrees[i].init(m, a[i]);
	}
	for(int i = 0; i < m; ++i){
		for(int j = 0;j<n; ++ j){
			rv[j] = a[j][i];
		}
		cTrees[i].init(n, rv);
	}
	for(int i = 0; i < k; ++i){
		char c;
		int h, y;
		cin >> c >> y >> h;
		y--;
		//for(int j = 0; j < r; ++j){
			int tmp;
			if(c == 'N'){
				cTrees[y].resIdx.clear();
				cTrees[y].glR = r;
				cTrees[y].getF(0, 0, n-1, h);
				for(auto tmp : cTrees[y].resIdx){
					cTrees[y].upd(0, 0, n-1, tmp, -1);
					rTrees[tmp].upd(0, 0, m-1, y, -1);
					//cerr << tmp << ' ' << y << '\n';
					a[tmp][y]--;
				}
			}
			if(c == 'S'){
				cTrees[y].resIdx.clear();
				cTrees[y].glR =r;
				cTrees[y].getL(0, 0, n-1, h);
				for(auto tmp : cTrees[y].resIdx){
					cTrees[y].upd(0, 0, n-1, tmp, -1);
					rTrees[tmp].upd(0, 0, m-1, y, -1);
					//cerr << tmp << ' ' <<  y<< '\n';
					a[tmp][y]--;
				}
			}
			if(c == 'W'){
				rTrees[y].resIdx.clear();
				rTrees[y].glR = r;
				rTrees[y].getF(0, 0, m-1, h);
				for(auto tmp : rTrees[y].resIdx){
					rTrees[y].upd(0, 0, m-1, tmp, -1);
					cTrees[tmp].upd(0, 0, n-1, y, -1);
					//cerr << y << ' ' << tmp << '\n';
					a[y][tmp] --;
				}
			}
			if(c == 'E'){
				rTrees[y].resIdx.clear();
				rTrees[y].glR = r;
				rTrees[y].getL(0, 0, m-1, h);
				for(auto tmp : rTrees[y].resIdx){
					rTrees[y].upd(0, 0, m-1, tmp, -1);
					cTrees[tmp].upd(0, 0, n-1, y, -1);
					//cerr << y << ' ' << tmp << '\n';
					a[y][tmp] --;}
			}
		//}
	}
	for(int i = 0; i < n; ++i){
		for(int j = 0; j < m; ++j){
			//cerr << a[i][j] << ' ';
		}
		//cerr << '\n';
	}
	cout << getMax();
}
/*4 8 2 6 2
1 1 1 1 1 1 1 1
1 2 3 1 1 1 3 1
1 2 1 1 3 1 1 1
1 1 1 1 1 1 1 2
N 2 2
W 2 2
W 2 3
E 2 1
S 4 1
S 7 1*/

Compilation message

ufo.cpp: In function 'int main()':
ufo.cpp:166:8: warning: unused variable 'tmp' [-Wunused-variable]
  166 |    int tmp;
      |        ^~~
# 결과 실행 시간 메모리 Grader output
1 Correct 115 ms 156908 KB Output is correct
2 Correct 99 ms 157036 KB Output is correct
3 Runtime error 320 ms 262144 KB Execution killed with signal 6 (could be triggered by violating memory limits)
4 Runtime error 315 ms 262144 KB Execution killed with signal 6 (could be triggered by violating memory limits)
5 Runtime error 293 ms 262144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 572 ms 262144 KB Execution killed with signal 6 (could be triggered by violating memory limits)
7 Runtime error 251 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 220 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 218 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 240 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 217 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 219 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 474 ms 262144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 212 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 224 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 215 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 486 ms 262144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 462 ms 262144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 222 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Runtime error 228 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)