oj.uz

Submission #74469

# Submission time Handle Problem Language Result Execution time Memory
74469 2018-09-02T06:56:06 Z gs18115 None (KOI17_shell) C++14
0 / 100
 2000 ms 53664 KB 
#include<iostream>
using namespace std;
typedef long long LL;
const LL MAXN=1510;
const LL n=2048;
LL FT[MAXN][MAXN];
void FI(const LL&i,LL j,const LL&dif)
{
    if(i==0||j==0)
        return;
    for(;j<MAXN;j+=j&-j)
        FT[i][j]+=dif;
    return;
}
void FS(const LL&i,LL j,LL&SC)
{
    SC=0;
    if(i==0||j==0)
        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 N;
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]=MAXN;
            E[j]=0;
        }
        cin>>C>>X>>Y;
        ch=C=='U'?1LL:-1LL;
        arr[X][Y]+=ch;
        sx=ex=X;
        sy=ey=Y;
        S[X]=Y;
        flag=N;
        flag1=flag2=true;
        while(ex<=N)
        {
            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(E[sx]>sy)
                        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,N,t1);
                    FS(sx+1,N,t2);
                    FS(sx+1,N-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;
                    }
                }
            }
        }
        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
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2045 ms 2424 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2075 ms 53664 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 54.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2045 ms 2424 KB Time limit exceeded
2 Halted 0 ms 0 KB -