Submission #168885

#	Time	Username	Problem	Language	Result	Execution time	Memory
168885		mhy908	조개 줍기 (KOI17_shell)	C++14	100 / 100	666 ms	44960 KiB

shell

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
const LL llinf=9000000000000000000;
const int inf=2000000000;
struct fenwick{
    LL tree[1520];
    LL sum(int i){
        LL ans=0;
        while(i){
            ans+=tree[i];
            i-=(i&-i);
        }
        return ans;
    }
    void update(int i, LL num){
        while(i<=1500){
            tree[i]+=num;
            i+=(i&-i);
        }
    }
}fen[1510];
int n;
LL arr[1510][1510];
LL ans;
LL get_arr(int x, int y){
    return arr[x][y]+fen[x].sum(y);
}
void query(int x, int y, LL u){
    vector<int> st, fin;
    st.resize(n+10);
    fin.resize(n+10);
    for(int i=x+1; i<=n; i++)st[i]=n+1;
    fin[x]=y;
    st[x]=y;
    for(int pvx=x, pvy=y;;){
        if(pvy<n&&max(get_arr(pvx-1, pvy+1), get_arr(pvx, pvy))+u==max(get_arr(pvx-1, pvy+1), get_arr(pvx, pvy)+u))pvy++;
        else pvx++;
        if(pvx>n)break;
        fin[pvx]=pvy;
    }
    for(int pvx=x, pvy=y;;){
        if(pvx<n&&max(get_arr(pvx+1, pvy-1), get_arr(pvx, pvy))+u==max(get_arr(pvx+1, pvy-1), get_arr(pvx, pvy)+u))pvx++;
        else pvy++;
        if(pvy>n||fin[pvx]<pvy)break;
        st[pvx]=min(st[pvx], pvy);
    }
    for(int i=x; i<=n; i++){
        if(st[i]>fin[i])break;
        ans+=(LL)(fin[i]-st[i]+1)*u;
        fen[i].update(st[i], u);
        fen[i].update(fin[i]+1, -u);
    }
}
int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            LL a;
            scanf("%lld", &a);
            arr[i][j]=max(arr[i-1][j], arr[i][j-1])+a;
            ans+=arr[i][j];
        }
    }
    printf("%lld\n", ans);
    for(int i=1; i<=n; i++){
        char c;
        int a, b;
        scanf(" %c %d %d", &c, &a, &b);
        if(c=='U')query(a, b, 1);
        else query(a, b, -1);
        printf("%lld\n", ans);
    }
}

Compilation message (stderr)

shell.cpp: In function 'int main()':
shell.cpp:63:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
shell.cpp:67:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%lld", &a);
             ~~~~~^~~~~~~~~~~~
shell.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c %d %d", &c, &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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