Submission #124490

#	Time	Username	Problem	Language	Result	Execution time	Memory
124490		DJ035	조개 줍기 (KOI17_shell)	C++14	100 / 100	487 ms	35660 KiB

shell

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int mx = 1505;

ll dpval = 0;
struct RRBIT{
    int n;
    ll *d;
    int *f;
    RRBIT(){}
    RRBIT(int n, ll *p, int *B):n(n),d(p),f(B){}
    
    void upd(int a, int b, int v){
        dpval += v * (b-a+1);
        for(;a<=n;a+=(a&-a)) f[a] += v;
        for(++b;b<=n;b+=(b&-b)) f[b] -= v;
    }
    ll gsum(int i){
        ll s = d[i];
        for(;i;i-=(i&-i)) s += f[i];
        return s;
    }
} I[mx];

ll dp[mx][mx], sh;
int BIT[mx][mx];

inline int t(int i, int j){
    return I[i].gsum(j);
}

int n;
int s[mx], e[mx];

void input(){
    cin >> n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin >> sh;
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + sh;
            dpval += dp[i][j];
        }
        I[i] = RRBIT(n, dp[i], BIT[i]);
    }
    cout << dpval << '\n';
}

void query(){
    char c;
    for(int i=1,x,y;i<=n;i++){
        cin >> c >> x >> y;
        c = (c == 'U');
        s[x] = y; e[x] = y + 1;
        int &sx = s[x], &ex = e[x];
        for(;ex <= n; ex++){
            if(x==1) continue;
            if( t(x, ex-1) + c <= t(x-1, ex) ) break;
            //if(c ? t(x,ex-1) < t(x-1,ex) : t(x,ex-1) <= t(x-1,ex)) break;
        }
        for(int j = x+1; j<=n; ++j){
            int &sj = s[j], &ej = e[j];
            sj = s[j-1]; ej = e[j-1];

            for(;1 < sj && sj < ej; sj++){
                
                if( t(j, sj-1) + !c <= t(j-1, sj) ) break;
                //if(c ? t(j,sj-1) <= t(j-1,sj) : t(j,sj-1) < t(j-1,sj)) break;

            }
            if(sj >= ej) break;

            for(;ej <= n; ej++){
                
                if( t(j, ej-1) + c <= t(j-1, ej) ) break;
                //if(c ? t(j,ej-1) < t(j-1,ej) : t(j,ej-1) <= t(j-1,ej)) break;
            }        
        }
        for(int j=x;j<=n;j++){
            if(s[j] >= e[j]) break;
            I[j].upd(s[j], e[j]-1, 2*c-1);
        }
        cout << dpval << '\n';
    }
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    input();
    query();
}

Compilation message (stderr)

shell.cpp: In function 'void query()':
shell.cpp:56:14: warning: unused variable 'sx' [-Wunused-variable]
         int &sx = s[x], &ex = e[x];
              ^~

• Subtask 1: 12 / 12
• Subtask 2: 34 / 34
• Subtask 3: 54 / 54