oj.uz

Submission #404434

# Submission time Handle Problem Language Result Execution time Memory
404434 2021-05-14T12:09:45 Z zaneyu None (KOI17_shell) C++14
100 / 100
 653 ms 38452 KB 
/*input
3

3 2 7

4 2 6

5 3 8

U 1 2

D 3 2

U 1 2
*/
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define MXTO(x,y) x=max(x,y)
#define pb push_back
#define f first
#define s second
#define ll long long
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define lowb(x) x&(-x)
const int maxn=1500+5;
int dp[maxn][maxn];
int arr[maxn][maxn];
int n;
ll ans=0;
void calc2(){
    REP1(i,n){
        REP1(j,n){
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])+arr[i][j];
            ans+=dp[i][j];
        }
    }
    cout<<ans<<'\n';
}
struct ft{
    ll bit[maxn];
    void upd(int p,int x){
        while(p<maxn){
            bit[p]+=x;
            p+=lowb(p);
        }
    }
    ll query(int p){
        ll ans=0;
        while(p){
            ans+=bit[p];
            p-=lowb(p);
        }
        return ans;
    }
    void upd(int l,int r,int x){
        upd(l,x);
        upd(r+1,-x);
    }
}bit[maxn];
map<pii,bool> changed;
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    cin>>n;
    REP1(i,n) REP1(j,n) cin>>arr[i][j];
    calc2();
    REP1(i,n) REP1(j,n) bit[i].upd(j,j,dp[i][j]);
    REP(i,n){
        char c;
        int x,y;
        cin>>c>>x>>y;
        int d=1;
        if(c=='D') d=-1;
        arr[x][y]+=d;
        int l=y,r=y;
        for(int i=x;i<=n;i++){
            while(l<r){
                dp[i][l]=max(bit[i].query(l-1),bit[i-1].query(l))+arr[i][l];
                if(bit[i].query(l)!=dp[i][l]) break;
                ++l;
            }
            bit[i].upd(l,n,d);
            while(r<=n){
                dp[i][r]=max(bit[i].query(r-1),bit[i-1].query(r))+arr[i][r];
                if(bit[i].query(r)-d==dp[i][r]) break;
                ++r;
            }
            bit[i].upd(r,n,-d);
            //cout<<l<<' '<<r<<'\n';
            ans+=d*(r-l);
        }
        changed.clear();
        cout<<ans<<'\n';
    }
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2380 KB Output is correct
2 Correct 4 ms 2380 KB Output is correct
3 Correct 5 ms 2380 KB Output is correct
4 Correct 4 ms 2380 KB Output is correct
5 Correct 5 ms 2340 KB Output is correct
6 Correct 4 ms 2380 KB Output is correct
7 Correct 3 ms 2380 KB Output is correct
8 Correct 4 ms 2380 KB Output is correct
9 Correct 4 ms 2372 KB Output is correct
10 Correct 3 ms 2380 KB Output is correct

Subtask #2
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 36940 KB Output is correct
2 Correct 246 ms 36856 KB Output is correct
3 Correct 327 ms 37052 KB Output is correct
4 Correct 459 ms 36988 KB Output is correct
5 Correct 413 ms 36952 KB Output is correct
6 Correct 245 ms 36916 KB Output is correct
7 Correct 248 ms 36904 KB Output is correct
8 Correct 422 ms 36932 KB Output is correct
9 Correct 424 ms 36868 KB Output is correct
10 Correct 398 ms 36948 KB Output is correct

Subtask #3
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2380 KB Output is correct
2 Correct 4 ms 2380 KB Output is correct
3 Correct 5 ms 2380 KB Output is correct
4 Correct 4 ms 2380 KB Output is correct
5 Correct 5 ms 2340 KB Output is correct
6 Correct 4 ms 2380 KB Output is correct
7 Correct 3 ms 2380 KB Output is correct
8 Correct 4 ms 2380 KB Output is correct
9 Correct 4 ms 2372 KB Output is correct
10 Correct 245 ms 36940 KB Output is correct
11 Correct 246 ms 36856 KB Output is correct
12 Correct 327 ms 37052 KB Output is correct
13 Correct 459 ms 36988 KB Output is correct
14 Correct 413 ms 36952 KB Output is correct
15 Correct 245 ms 36916 KB Output is correct
16 Correct 248 ms 36904 KB Output is correct
17 Correct 422 ms 36932 KB Output is correct
18 Correct 424 ms 36868 KB Output is correct
19 Correct 398 ms 36948 KB Output is correct
20 Correct 3 ms 2380 KB Output is correct
21 Correct 479 ms 36928 KB Output is correct
22 Correct 477 ms 36968 KB Output is correct
23 Correct 489 ms 36952 KB Output is correct
24 Correct 596 ms 36948 KB Output is correct
25 Correct 653 ms 37492 KB Output is correct
26 Correct 601 ms 37584 KB Output is correct
27 Correct 262 ms 36960 KB Output is correct
28 Correct 331 ms 37020 KB Output is correct
29 Correct 497 ms 38176 KB Output is correct
30 Correct 487 ms 38316 KB Output is correct
31 Correct 609 ms 38336 KB Output is correct
32 Correct 650 ms 38452 KB Output is correct
33 Correct 249 ms 36924 KB Output is correct
34 Correct 436 ms 37060 KB Output is correct