# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
38824 | alenam0161 | UFO (IZhO14_ufo) | C++14 | 2000 ms | 150456 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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_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(){
scanf("%d%d%d%d%d",&ro,&cl,&r,&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);
scanf(" %c %d %d",&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;
}
}
}
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 (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |