| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 171948 |
2019-12-30T16:45:35 Z |
Swan |
UFO (IZhO14_ufo) |
C++14 |
|
69 ms |
63992 KB |
#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;
/*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){
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){
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)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)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;
a = get_max_r(dir,num,v*2,l,m,le,re,need);
b = get_max_r(dir,num,v*2+1,m+1,r,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)){
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)){
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)){
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)){
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);
tree[2].resize(n);
tree[3].resize(m);
for(int i(0); i < n;i++){
tree[0][i].resize(4*m);
tree[2][i].resize(4*m);
}
for(int i(0); i < m;i++){
tree[1][i].resize(4*n);
tree[3][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; cin >> c;
int x,need; cin >> 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;
}
/*
*/
Compilation message
ufo.cpp:164:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main(){
^
ufo.cpp: In function 'int main()':
ufo.cpp:165:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d%d",&n,&m,&r,&k,&p);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ufo.cpp:182:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int val; scanf("%d",&val);
~~~~~^~~~~~~~~~~
ufo.cpp:171:19: warning: array subscript is above array bounds [-Warray-bounds]
tree[3].resize(m);
~~~~~~~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
2 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
2 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Runtime error |
2 ms |
632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
3 ms |
1144 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
7 ms |
4444 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
17 ms |
13944 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
17 ms |
13944 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
14 ms |
11128 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
17 ms |
14072 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 |
Runtime error |
17 ms |
14840 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Runtime error |
17 ms |
13944 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 13 |
Runtime error |
30 ms |
22648 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 14 |
Runtime error |
18 ms |
14840 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 15 |
Runtime error |
17 ms |
13944 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 16 |
Runtime error |
18 ms |
14840 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 17 |
Runtime error |
29 ms |
22648 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 18 |
Runtime error |
31 ms |
23416 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 19 |
Runtime error |
22 ms |
19640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 20 |
Runtime error |
69 ms |
63992 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
