Submission #38822

# Submission time Handle Problem Language Result Execution time Memory
38822 2018-01-06T19:15:08 Z alenam0161 UFO (IZhO14_ufo) C++14
5 / 100
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