oj.uz

Submission #188566

# Submission time Handle Problem Language Result Execution time Memory
188566 2020-01-13T09:12:44 Z knon0501 None (KOI17_shell) C++14
0 / 100
 218 ms 40776 KB 
#include <bits/stdc++.h>
using namespace std;
int n,nn;
int seg[1501][6000];
int a[1501][1501];
int dp[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";
    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)){
                r=j;
                dp[y][j]=f(y,j)+k;
            }
        }
        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);

        }
        cout<<ans<<"\n";
    }
    return 0;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 1912 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 40776 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 54.0

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