| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 38822 |
2018-01-06T19:15:08 Z |
alenam0161 |
UFO (IZhO14_ufo) |
C++14 |
|
2000 ms |
98188 KB |
#include <bits/stdc++.h>
using namespace std;
const int inf =1e9;
int ro,cl;
int **a;
int **col,**row;
void build_col(int cl,int l = 1,int r = ro,int v = 1){
if(l==r){
col[cl][v]=a[l][cl];
}
else{
int m=(l+r)/2;
build_col(cl,l,m,v+v);
build_col(cl,m+1,r,v+v+1);
col[cl][v]=max(col[cl][v+v],col[cl][v+v+1]);
}
}
void build_row(int R,int l = 1,int r = cl,int v = 1){
if(l==r){
row[R][v]=a[R][l];
}
else{
int m=(l+r)/2;
build_row(R,l,m,v+v);
build_row(R,m+1,r,v+v+1);
row[R][v]=max(row[R][v+v],row[R][v+v+1]);
}
}
void update_row(int rr,int val,int pos,int l=1,int r = cl,int v = 1){
if(l==r){
row[rr][v]=val;
}
else{
int m=(l+r)/2;
if(pos<=m)update_row(rr,val,pos,l,m,v+v);
else update_row(rr,val,pos,m+1,r,v+v+1);
row[rr][v]=max(row[rr][v+v],row[rr][v+v+1]);
}
}
void update_col(int cc,int val,int pos,int l=1,int r = ro,int v = 1){
if(l==r){
col[cc][v]=val;
}
else{
int m=(l+r)/2;
if(pos<=m)update_col(cc,val,pos,l,m,v+v);
else update_col(cc,val,pos,m+1,r,v+v+1);
col[cc][v]=max(col[cc][v+v],col[cc][v+v+1]);
}
}
int get_rowl(int rr,int tl,int tr,int high,int l = 1,int r = cl,int v = 1){
if(tl<=l&&r<=tr){
if(row[rr][v]>=high){
if(l==r)return l;
int m=(l+r)/2;
if(row[rr][v+v]>=high)return get_rowl(rr,tl,tr,high,l,m,v+v);
else return get_rowl(rr,tl,tr,high,m+1,r,v+v+1);
}
else{
return inf;
}
}
else{
int m=(l+r)/2;
int gf=inf;
if(tl<=m)gf=get_rowl(rr,tl,tr,high,l,m,v+v);
if(gf!=inf)return gf;
return get_rowl(rr,tl,tr,high,m+1,r,v+v+1);
}
}
int get_rowr(int rr,int tl,int tr,int high,int l = 1,int r = cl,int v = 1){
if(tl<=l&&r<=tr){
if(row[rr][v]>=high){
if(l==r)return l;
int m=(l+r)/2;
if(row[rr][v+v+1]>=high)return get_rowr(rr,tl,tr,high,m+1,r,v+v+1);
else return get_rowr(rr,tl,tr,high,l,m,v+v);
}
else{
return inf;
}
}
else{
int m=(l+r)/2;
int gf=inf;
if(tr>m)gf=get_rowr(rr,tl,tr,high,m+1,r,v+v+1);
if(gf!=inf)return gf;
return get_rowr(rr,tl,tr,high,l,m,v+v);
}
}
int get_coll(int cc,int tl,int tr,int high,int l = 1,int r = ro,int v = 1){
if(tl<=l&&r<=tr){
if(col[cc][v]>=high){
if(l==r)return l;
int m=(l+r)/2;
if(col[cc][v+v]>=high)return get_coll(cc,tl,tr,high,l,m,v+v);
else return get_coll(cc,tl,tr,high,m+1,r,v+v+1);
}
else return inf;
}
else{
int m=(l+r)/2;
int gf=inf;
if(tl<=m)gf=get_coll(cc,tl,tr,high,l,m,v+v);
if(gf!=inf)return gf;
return get_coll(cc,tl,tr,high,m+1,r,v+v+1);
}
}
int get_colr(int cc,int tl,int tr,int high,int l = 1,int r = ro,int v = 1){
if(tl<=l&&r<=tr){
if(col[cc][v]>=high){
if(l==r)return l;
int m=(l+r)/2;
if(col[cc][v+v+1]>=high)return get_coll(cc,tl,tr,high,m+1,r,v+v+1);
else return get_colr(cc,tl,tr,high,l,m,v+v);
}
else return inf;
}
else{
int m=(l+r)/2;
int gf=inf;
if(tr>m)gf=get_colr(cc,tl,tr,high,m+1,r,v+v+1);
if(gf!=inf)return gf;
return get_colr(cc,tl,tr,high,l,m,v+v);
}
}
void update(int x,int r){
a[x][r]--;
update_col(r,a[x][r],x);
update_row(x,a[x][r],r);
}
int main(){
int r,k,p;
scanf("%d%d%d%d%d",&ro,&cl,&r,&k,&p);
a=new int*[ro+15];
for(int i=0;i<=ro;++i)a[i]=new int[cl+15];
for(int i=0;i<=ro;++i)for(int j=0;j<=cl;++j)a[i][j]=0;
for(int i=1;i<=cl;++i)for(int j=1;j<=cl;++j){
scanf("%d",&a[i][j]);
}
col=new int*[cl+10];
for(int i=0;i<=cl;++i)col[i]=new int[ro*10];
row=new int*[ro+10];
for(int i=0;i<=ro;++i)row[i]=new int[cl*10];
for(int i=1;i<=cl;++i)build_col(i);
for(int i=1;i<=ro;++i)build_row(i);
for(int i=1;i<=k;++i){
char u;
int coord,high;
cin>>u>>coord>>high;
if(u=='N'){
int l=1;
for(int j=1;j<=r;++j){
int index=get_coll(coord,l,ro,high);
if(index==inf)break;
l=index+1;
update(index,coord);
if(l>ro)break;
}
}
else if(u=='S'){
int r=ro;
for(int j=1;j<=r;++j){
int index=get_colr(coord,1,r,high);
if(index==inf)break;
update(index,coord);
r=index-1;
if(r<1)break;
}
}
else if(u=='W'){
int l=1;
for(int j=1;j<=r;++j){
int index=get_rowl(coord,l,cl,high);
if(index==inf)break;
l=index+1;
update(coord,index);
if(l>cl)break;
}
}
else {
int r=cl;
for(int j=1;j<=r;++j){
int index=get_rowr(coord,1,r,high);
if(index==inf)break;
r=index-1;
update(coord,index);
if(r<1)break;
}
}
}
int ans=0;
for(int i=1;i<=ro;++i)
for(int j=1;j<=cl;++j){
a[i][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]-a[i][j-p]+a[i-p][j-p]);
}
cout<<ans<<endl;
return 0;
}
Compilation message
ufo.cpp: In function 'int main()':
ufo.cpp:136:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d%d",&ro,&cl,&r,&k,&p);
^
ufo.cpp:141:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&a[i][j]);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2020 KB |
Output is correct |
| 2 |
Runtime error |
0 ms |
2020 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Incorrect |
3 ms |
2284 KB |
Output isn't correct |
| 4 |
Incorrect |
29 ms |
2944 KB |
Output isn't correct |
| 5 |
Execution timed out |
2000 ms |
6428 KB |
Execution timed out |
| 6 |
Incorrect |
1436 ms |
42444 KB |
Output isn't correct |
| 7 |
Execution timed out |
2000 ms |
6332 KB |
Execution timed out |
| 8 |
Execution timed out |
2000 ms |
6332 KB |
Execution timed out |
| 9 |
Execution timed out |
2000 ms |
6136 KB |
Execution timed out |
| 10 |
Execution timed out |
2000 ms |
6332 KB |
Execution timed out |
| 11 |
Execution timed out |
2000 ms |
6268 KB |
Execution timed out |
| 12 |
Execution timed out |
2000 ms |
6332 KB |
Execution timed out |
| 13 |
Incorrect |
209 ms |
98188 KB |
Output isn't correct |
| 14 |
Execution timed out |
2000 ms |
6268 KB |
Execution timed out |
| 15 |
Execution timed out |
2000 ms |
6332 KB |
Execution timed out |
| 16 |
Execution timed out |
2000 ms |
6268 KB |
Execution timed out |
| 17 |
Incorrect |
306 ms |
98188 KB |
Output isn't correct |
| 18 |
Incorrect |
193 ms |
86416 KB |
Output isn't correct |
| 19 |
Execution timed out |
2000 ms |
6724 KB |
Execution timed out |
| 20 |
Execution timed out |
2000 ms |
9836 KB |
Execution timed out |
