Submission #38825

# Submission time Handle Problem Language Result Execution time Memory
38825 2018-01-06T19:49:20 Z alenam0161 UFO (IZhO14_ufo) C++14
25 / 100
2000 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);
}

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);
       //         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<=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;
            }
        }
  /*      for(int ii=1;ii<=ro;++ii)
        {
            for(int jj=1;jj<=cl;++jj){
                cout<<a[ii][jj]<< " ";
            }
            cout<<endl;
        }
*/
    }
    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:140: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:135: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:140:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&a[i][j]);
                             ^
ufo.cpp:152:43: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c %d %d",&u,&coord,&high);
                                           ^
# 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 Incorrect 0 ms 2284 KB Output isn't correct
4 Incorrect 46 ms 2944 KB Output isn't correct
5 Execution timed out 2000 ms 6756 KB Execution timed out
6 Execution timed out 2000 ms 44336 KB Execution timed out
7 Execution timed out 2000 ms 95072 KB Execution timed out
8 Incorrect 1723 ms 95072 KB Output isn't correct
9 Correct 703 ms 91584 KB Output is correct
10 Execution timed out 2000 ms 95072 KB Execution timed out
11 Correct 543 ms 92948 KB Output is correct
12 Execution timed out 2000 ms 95072 KB Execution timed out
13 Execution timed out 2000 ms 107560 KB Execution timed out
14 Execution timed out 2000 ms 92948 KB Execution timed out
15 Execution timed out 2000 ms 95072 KB Execution timed out
16 Incorrect 1926 ms 92948 KB Output isn't correct
17 Execution timed out 2000 ms 107560 KB Execution timed out
18 Incorrect 1779 ms 97636 KB Output isn't correct
19 Execution timed out 2000 ms 100520 KB Execution timed out
20 Correct 1689 ms 150456 KB Output is correct