Submission #38826

#	Time	Username	Problem	Language	Result	Execution time	Memory
38826		alenam0161	UFO (IZhO14_ufo)	C++14	100 / 100	1439 ms	150456 KiB

ufo

#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 (stderr)

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]);
                             ^

• Subtask 1: 100 / 100