oj.uz

Submission #404416

# Submission time Handle Problem Language Result Execution time Memory
404416 2021-05-14T11:44:40 Z zaneyu None (KOI17_shell) C++14
0 / 100
 226 ms 20496 KB 
/*input
3
 
1 0 0 
1 1 0
0 0 0
 
D 1 1
 
D 2 1
 
D 2 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{
    int bit[maxn];
    void upd(int p,int x){
        while(p<maxn){
            bit[p]+=x;
            p+=lowb(p);
        }
    }
    int query(int p){
        int 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;
bool change(int i,int j){
    if(changed.count({i,j})) return changed[{i,j}];
    int pv=dp[i][j];
    dp[i][j]=max(dp[i-1][j],dp[i][j-1])+arr[i][j];
    return changed[{i,j}]=dp[i][j]!=pv;
}
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    cin>>n;
    REP1(i,n) REP1(j,n) cin>>arr[i][j];
    calc2();
 
    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(r<=n and change(i,r)) ++r;
            while(l<r and !change(i,l)) ++l;
            //cout<<l<<' '<<r<<'\n';
            bit[i].upd(l,r-1,d);
            ans+=d*(r-l);
        }
        changed.clear();
        cout<<ans<<'\n';
    }
}

Subtask #1
0 / 12.0

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

Subtask #2
0 / 34.0

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

Subtask #3
0 / 54.0

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