Submission #74477

#	Time	Username	Problem	Language	Result	Execution time	Memory
74477		gs18115	조개 줍기 (KOI17_shell)	C++14	100 / 100	903 ms	146608 KiB

shell

#include<iostream>
using namespace std;
typedef long long LL;
const LL MAXN=1510;
const LL n=2048;
LL FT[MAXN][n+10];
LL N;
void FI(const LL&i,LL j,const LL&dif)
{
    if(i<=0||j<=0||i>N||j>N)
        return;
    for(;j<=n;j+=j&-j)
        FT[i][j]+=dif;
    return;
}
void FS(const LL&i,LL j,LL&SC)
{
    SC=0;
    if(i<=0||j<=0||i>N||j>N)
        return;
    for(;j>0;j=j&(j-1))
        SC+=FT[i][j];
    return;
}
LL arr[MAXN][MAXN];
LL dp[MAXN][MAXN];
LL S[MAXN],E[MAXN];
char C;
LL ch;
LL A,B;
LL i,j;
LL X,Y;
LL sx,ex,sy,ey;
LL flag;
bool flag1,flag2;
LL ans;
LL t1,t2,t3;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>N;
    for(i=1;i<=N;i++)
        for(j=1;j<=N;j++)
            cin>>arr[i][j];
    for(i=1;i<=N;i++)
    {
        for(j=1;j<=N;j++)
        {
            dp[i][j]=arr[i][j]+max(dp[i-1][j],dp[i][j-1]);
            FI(i,j,dp[i][j]-dp[i][j-1]);
            ans+=dp[i][j];
        }
    }
    cout<<ans<<endl;
    for(i=0;i<N;i++)
    {
        for(j=1;j<=N;j++)
        {
            S[j]=N+1;
            E[j]=0;
        }
        cin>>C>>X>>Y;
        ch=C=='U'?1LL:-1LL;
        arr[X][Y]+=ch;
        sx=ex=X;
        sy=ey=Y;
        S[X]=E[X]=Y;
        flag=N;
        flag1=flag2=true;
        while(ex<=N&&(flag1||flag2))
        {
            if(flag1)
            {
                if(sy<N)
                {
                    FS(sx,sy,t1);
                    FS(sx+1,sy,t2);
                    FS(sx+1,sy-1,t3);
                    if(t2!=max(t1+ch,t3)+arr[sx+1][sy])
                        S[++sx]=sy;
                    else if(sx!=ex)
                        sy++;
                    else
                    {
                        FS(sx,sy+1,t2);
                        FS(sx-1,sy+1,t3);
                        if(t2!=max(t1+ch,t3)+arr[sx][sy+1])
                            sy++;
                        else
                        {
                            flag=sx;
                            flag1=false;
                        }
                    }
                }
                else
                {
                    FS(sx,sy,t1);
                    FS(sx+1,sy,t2);
                    FS(sx+1,sy-1,t3);
                    if(t2!=max(t1+ch,t3)+arr[sx+1][sy])
                        S[++sx]=sy;
                    else
                    {
                        flag=sx;
                        flag1=false;
                    }
                }
            }
            if(flag2)
            {
                if(ey<N)
                {
                    FS(ex,ey,t1);
                    FS(ex,ey+1,t2);
                    FS(ex-1,ey+1,t3);
                    if(t2!=max(t1+ch,t3)+arr[ex][ey+1])
                        ey++;
                    else
                    {
                        E[ex]=ey;
                        if(ey>S[ex+1])
                            ex++;
                        else
                        {
                            FS(ex+1,ey,t2);
                            FS(ex+1,ey-1,t3);
                            if(t2!=max(t1+ch,t3)+arr[ex+1][ey])
                                ex++;
                            else
                                flag2=false;
                        }
                    }
                }
                else
                {
                    E[ex]=ey;
                    if(ey>S[ex+1])
                        ex++;
                    else
                    {
                        FS(ex+1,ey,t2);
                        FS(ex+1,ey-1,t3);
                        if(t2!=max(t1+ch,t3)+arr[ex+1][ey])
                            ex++;
                        else
                            flag2=false;
                    }
                }
            }
            S[sx]=min(S[sx],sy);
            E[ex]=ey;
        }
        for(j=X;j<=flag;j++)
        {
            ans+=ch*(E[j]-S[j]+1);
            FI(j,S[j],ch);
            FI(j,E[j]+1,-ch);
        }
        cout<<ans<<'\n';
    }
    cout<<endl;
    return 0;
}

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