Submission #404416

#	Time	Username	Problem	Language	Result	Execution time	Memory
404416		zaneyu	조개 줍기 (KOI17_shell)	C++14	0 / 100	226 ms	20496 KiB

shell

/*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
• Subtask 2: 0 / 34
• Subtask 3: 0 / 54