oj.uz

Submission #188605

# Submission time Handle Problem Language Result Execution time Memory
188605 2020-01-13T09:33:02 Z knon0501 None (KOI17_shell) C++14
100 / 100
 1146 ms 53692 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)){
                dp[y][j]=f(y,j)+k;
                r=j;
            }
            else
                break;
        }
        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
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1784 KB Output is correct
2 Correct 5 ms 1784 KB Output is correct
3 Correct 5 ms 1784 KB Output is correct
4 Correct 6 ms 1784 KB Output is correct
5 Correct 6 ms 1784 KB Output is correct
6 Correct 6 ms 1784 KB Output is correct
7 Correct 4 ms 1784 KB Output is correct
8 Correct 4 ms 1788 KB Output is correct
9 Correct 5 ms 1712 KB Output is correct
10 Correct 5 ms 1784 KB Output is correct

Subtask #2
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 40800 KB Output is correct
2 Correct 206 ms 40564 KB Output is correct
3 Correct 251 ms 49272 KB Output is correct
4 Correct 236 ms 38840 KB Output is correct
5 Correct 235 ms 38732 KB Output is correct
6 Correct 207 ms 40700 KB Output is correct
7 Correct 201 ms 40568 KB Output is correct
8 Correct 246 ms 38904 KB Output is correct
9 Correct 245 ms 38816 KB Output is correct
10 Correct 234 ms 38728 KB Output is correct

Subtask #3
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1784 KB Output is correct
2 Correct 5 ms 1784 KB Output is correct
3 Correct 5 ms 1784 KB Output is correct
4 Correct 6 ms 1784 KB Output is correct
5 Correct 6 ms 1784 KB Output is correct
6 Correct 6 ms 1784 KB Output is correct
7 Correct 4 ms 1784 KB Output is correct
8 Correct 4 ms 1788 KB Output is correct
9 Correct 5 ms 1712 KB Output is correct
10 Correct 212 ms 40800 KB Output is correct
11 Correct 206 ms 40564 KB Output is correct
12 Correct 251 ms 49272 KB Output is correct
13 Correct 236 ms 38840 KB Output is correct
14 Correct 235 ms 38732 KB Output is correct
15 Correct 207 ms 40700 KB Output is correct
16 Correct 201 ms 40568 KB Output is correct
17 Correct 246 ms 38904 KB Output is correct
18 Correct 245 ms 38816 KB Output is correct
19 Correct 234 ms 38728 KB Output is correct
20 Correct 289 ms 53272 KB Output is correct
21 Correct 297 ms 53372 KB Output is correct
22 Correct 297 ms 53364 KB Output is correct
23 Correct 1107 ms 53372 KB Output is correct
24 Correct 1146 ms 53364 KB Output is correct
25 Correct 1098 ms 53004 KB Output is correct
26 Correct 242 ms 40580 KB Output is correct
27 Correct 280 ms 49392 KB Output is correct
28 Correct 296 ms 53564 KB Output is correct
29 Correct 301 ms 53332 KB Output is correct
30 Correct 1090 ms 53648 KB Output is correct
31 Correct 1059 ms 53692 KB Output is correct
32 Correct 206 ms 40704 KB Output is correct
33 Correct 234 ms 38908 KB Output is correct
34 Correct 5 ms 1784 KB Output is correct