| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 171973 | Swan | UFO (IZhO14_ufo) | C++14 | 2061 ms | 78632 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define stop system("pause")
#define stop2 char o; cin >> o
#define INP freopen("pcb.in","r",stdin)
#define OUTP freopen ("pcb.out","w",stdout)
//#define int long long
using namespace std;
const int maxn = 100004;
int n,m,r,k,p;
bool f;
/*WE-0 NS-1*/
vector<vector<int> > tree[2];
vector<vector<int> > pref;
void increment(int dir,int num,int v,int l,int r,int need,int val){
if(l == r){
tree[dir][num][v]+=val;
return;
}
int m = (l+r)/2;
if(need<=m)increment(dir,num,v*2,l,m,need,val);
else increment(dir,num,v*2+1,m+1,r,need,val);
tree[dir][num][v] = max(tree[dir][num][v*2],tree[dir][num][v*2+1]);
}
int find_on_segm_l(int dir,int num,int v,int l,int r,int need){
if(l == r){
f = 1;
return l;
}
int m = (l+r)/2;
if(tree[dir][num][v*2]>=need)return find_on_segm_l(dir,num,v*2,l,m,need);
else if(tree[dir][num][v*2+1]>=need)return find_on_segm_l(dir,num,v*2+1,m+1,r,need);
else return -1;
}
int find_on_segm_r(int dir,int num,int v,int l,int r,int need){
if(l == r){
f = 1;
return l;
}
int m = (l+r)/2;
if(tree[dir][num][v*2+1]>=need)return find_on_segm_r(dir,num,v*2+1,m+1,r,need);
else if(tree[dir][num][v*2]>=need)return find_on_segm_r(dir,num,v*2,l,m,need);
else return -1;
}
int get_max_l(int dir,int num,int v,int l,int r,int le,int re,int need){
if(l >= le && r <= re ){
if(tree[dir][num][v]>=need && !f)return find_on_segm_l(dir,num,v,l,r,need);
else return -1;
}
if(l > re || r < le)return -1;
int m = (l+r)/2;
int a,b;
a = get_max_l(dir,num,v*2,l,m,le,re,need);
b = get_max_l(dir,num,v*2+1,m+1,r,le,re,need);
if(a!= -1)return a;
else return b;
}
int get_max_r(int dir,int num,int v,int l,int r,int le,int re,int need){
if(l >= le && r <= re){
if(tree[dir][num][v]>=need && !f)return find_on_segm_r(dir,num,v,l,r,need);
else return -1;
}
if(l > re || r < le)return -1;
int m = (l+r)/2;
int a,b;
b = get_max_r(dir,num,v*2+1,m+1,r,le,re,need);
a = get_max_r(dir,num,v*2,l,m,le,re,need);
if(b!= -1)return b;
else return a;
}
int get_cell(int v,int l,int r,int x,int y){
if(l == r)return tree[0][x][v];
int m = (l+r)/2;
if(y<=m)return get_cell(v*2,l,m,x,y);
else return get_cell(v*2+1,m+1,r,x,y);
}
void update_cell(int x,int y,int val){
increment(0,x,1,0,m-1,y,val);
increment(1,y,1,0,n-1,x,val);
}
void solve_w(int x,int need){
int cnt = r;
int l,r;l = 0;r = m-1;
while(cnt && (l!=m)){
f = 0;
int w = get_max_l(0,x,1,0,m-1,l,r,need);
if(w == -1)break;
cnt--;
l = w;
update_cell(x,l,-1);
l++;
}
}
void solve_e(int x,int need){
int cnt = r;
int l,r;l = 0;r = m-1;
while(cnt && (r>=0)){
f = 0;
int w = get_max_r(0,x,1,0,m-1,l,r,need);
if(w == -1)break;
cnt--;
r = w;
update_cell(x,r,-1);
r--;
}
}
void solve_n(int x,int need){
int cnt = r;
int l,r;l = 0;r = n-1;
while(cnt && (l!=n)){
f = 0;
int w = get_max_l(1,x,1,0,n-1,l,r,need);
if(w == -1)break;
cnt--;
l = w;
update_cell(l,x,-1);
l++;
}
}
void solve_s(int x,int need){
int cnt = r;
int l,r;l = 0;r = n-1;
while(cnt && (r>=0)){
f = 0;
int w = get_max_r(1,x,1,0,n-1,l,r,need);
if(w == -1)break;
cnt--;
r = w;
update_cell(r,x,-1);
r--;
}
}
void print(){
for(int i(0); i < n;i++){
for(int j(0); j < m;j++){
int now = get_cell(1,0,m-1,i,j);
int tox = i+1;int toy = j+1;
pref[tox][toy] = now;
pref[tox][toy]+=pref[tox-1][toy];
pref[tox][toy]+=pref[tox][toy-1];
pref[tox][toy]-=pref[tox-1][toy-1];
}
}
}
int get_sum(int x1,int y1,int x2,int y2){
int res = 0;
res+=pref[x2][y2];
res-=pref[x2][y1-1];
res-=pref[x1-1][y2];
res+=pref[x1-1][y1-1];
return res;
}
main(){
scanf("%d%d%d%d%d",&n,&m,&r,&k,&p);
pref.resize(n+2);
for(int i(0); i <= n;i++)pref[i].resize(m+2);
tree[0].resize(n);
tree[1].resize(m);
for(int i(0); i < n;i++){
tree[0][i].resize(4*m);
}
for(int i(0); i < m;i++){
tree[1][i].resize(4*n);
}
for(int i(0); i < n;i++){
for(int j(0); j < m;j++){
int val; scanf("%d",&val);
update_cell(i,j,val);
}
}
for(int i(0); i < k;i++){
char c; scanf(" %c",&c);
int x,need; scanf("%d%d",&x,&need);
x--;
if(c == 'W')solve_w(x,need);
if(c == 'E')solve_e(x,need);
if(c == 'N')solve_n(x,need);
if(c == 'S')solve_s(x,need);
}
print();
int ans = 0;
for(int i(1);i<=n;i++){
for(int j(1);j<=m;j++){
int x1 = i;
int y1 = j;
int x2 = i+p-1;
int y2 = j+p-1;
if(x2 <= n && y2<=m)ans = max(ans,get_sum(x1,y1,x2,y2));
}
}
printf("%d",ans);
return 0;
}
/*
*/
컴파일 시 표준 에러 (stderr) 메시지
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||