| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 38826 |
2018-01-06T19:55:56 Z |
alenam0161 |
UFO (IZhO14_ufo) |
C++14 |
|
1439 ms |
150456 KB |
#include <bits/stdc++.h>
using namespace std;
const int inf =1e9;
int ro,cl,p,k,r;
long long **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_colr(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);
}
void printt(){
for(int ii=1;ii<=ro;++ii)
{
for(int jj=1;jj<=cl;++jj){
cout<<a[ii][jj]<< " ";
}
cout<<endl;
}
}
int main(){
int how;
scanf("%d%d%d%d%d",&ro,&cl,&how,&k,&p);
a=new long long*[ro+15];
for(int i=0;i<=ro;++i)a[i]=new long long[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<=ro;++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;
// scanf("%c",&u);
cin>>u>>coord>>high;
//scanf(" %c %d %d",&u,&coord,&high);
if(u=='N'){
int l=1;
for(int j=1;j<=how;++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<=how;++j){
int index=get_colr(coord,1,r,high);
// cout<<r<<" "<<coord<<" "<<high<<" "<<index<<endl;
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<=how;++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<=how;++j){
int index=get_rowr(coord,1,r,high);
if(index==inf)break;
r=index-1;
update(coord,index);
if(r<1)break;
}
}
}
long long 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:149:28: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
scanf("%d",&a[i][j]);
^
ufo.cpp:144:43: 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,&how,&k,&p);
^
ufo.cpp:149: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 |
Correct |
0 ms |
2020 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2284 KB |
Output is correct |
| 4 |
Correct |
19 ms |
2944 KB |
Output is correct |
| 5 |
Correct |
159 ms |
6756 KB |
Output is correct |
| 6 |
Correct |
299 ms |
44336 KB |
Output is correct |
| 7 |
Correct |
463 ms |
95072 KB |
Output is correct |
| 8 |
Correct |
356 ms |
95072 KB |
Output is correct |
| 9 |
Correct |
656 ms |
91584 KB |
Output is correct |
| 10 |
Correct |
823 ms |
95072 KB |
Output is correct |
| 11 |
Correct |
603 ms |
92948 KB |
Output is correct |
| 12 |
Correct |
793 ms |
95072 KB |
Output is correct |
| 13 |
Correct |
1043 ms |
107560 KB |
Output is correct |
| 14 |
Correct |
829 ms |
92948 KB |
Output is correct |
| 15 |
Correct |
929 ms |
95072 KB |
Output is correct |
| 16 |
Correct |
456 ms |
92948 KB |
Output is correct |
| 17 |
Correct |
1439 ms |
107560 KB |
Output is correct |
| 18 |
Correct |
476 ms |
97636 KB |
Output is correct |
| 19 |
Correct |
586 ms |
100520 KB |
Output is correct |
| 20 |
Correct |
1143 ms |
150456 KB |
Output is correct |
