oj.uz

Submission #188576

# Submission time Handle Problem Language Result Execution time Memory
188576 2020-01-13T09:17:37 Z knon0501 None (KOI17_shell) C++14
0 / 100
 218 ms 40796 KB 
#include <bits/stdc++.h>
using namespace std;
int n,nn;
int seg[1501][6000];
int a[1501][1501];
int dp[1501][1501];
int dy[1501][1501];
inline int f(int y,int x){
    int ret=0;
    for(int i=nn+x-1 ; i>=1 ; i/=2)ret+=seg[y][i];
    return ret;
}
void upd(int y,int l,int r,int lef,int rig,int lev,int k){
    if(l<=lef && rig<=r){
        seg[y][lev]+=k;
        return;
    }
    if(r<lef || l>rig)return;
    int mid=(lef+rig)/2;
    upd(y,l,r,lef,mid,lev*2,k);
    upd(y,l,r,mid+1,rig,lev*2+1,k);
}
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cin>>n;
    int i,j;

    for(i=1 ; i<=n ; i++)for(j=1 ; j<=n ; j++)cin>>a[i][j];
    for(i=1 ; i<=n ; i++)for(j=1 ; j<=n ; j++)dp[i][j]=max(dp[i-1][j],dp[i][j-1])+a[i][j];

    for(nn=1 ; nn<n ; nn*=2);
    long long ans=0;

    for(i=1 ; i<=n ; i++)
        for(j=1 ; j<=n ; j++)
            seg[i][nn+j-1]=dp[i][j],ans+=dp[i][j];

    cout<<ans<<"\n";
    long long ans2=ans;
    for(i=1 ; i<=n ; i++){
        char c;
        int y,x;
        int k=1;
        cin>>c>>y>>x;
        if(c=='U')a[y][x]++;
        else{
            k=-1;
            a[y][x]--;
        }
        int l=x;
        int r=x;
        dp[y][x]=f(y,x)+k;
        for(j=x+1 ; j<=n ; j++){
            if(max(f(y-1,j),dp[y][j-1])+a[y][j]!=f(y,j)){
                dp[y][j]=f(y,j)+k;
                r=j;
            }
        }
        r++;
        ans+=(r-l)*k;
        upd(y,l,r-1,1,nn,1,k);
        for(j=y+1 ; j<=n ; j++){
            while(l<=n && max(f(j,l-1),f(j-1,l))+a[j][l]==f(j,l))l++;
            if(l>n)break;
            dp[j][r-1]=f(j,r-1)+k;
            while(r<=n && max(dp[j][r-1],f(j-1,r))+a[j][r]!=f(j,r)){
                dp[j][r]=f(j,r)+k;
                r++;
            }
            ans+=(r-l)*k;
            upd(j,l,r-1,1,nn,1,k);

        }
        /*
        for(int ii=1 ; ii<=n ; ii++){
            for(int jj=1 ; jj<=n ; jj++){
                dy[ii][jj]=max(dy[ii][jj-1],dy[ii-1][jj])+a[ii][jj];
            }
        }*/
        cout<<ans<<"\n";
       /// cout<<ans<<" "<<ans2<<"\n";
    }
    return 0;
}

Compilation message

shell.cpp: In function 'int main()':
shell.cpp:40:15: warning: unused variable 'ans2' [-Wunused-variable]
     long long ans2=ans;
               ^~~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1784 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 218 ms 40796 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 54.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1784 KB Output isn't correct
2 Halted 0 ms 0 KB -