oj.uz

Submission #74464

# Submission time Handle Problem Language Result Execution time Memory
74464 2018-09-02T06:45:21 Z gs18115 None (KOI17_shell) C++14
0 / 100
 222 ms 53788 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,x,y;
LL flag;
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;
        x=X;
        y=Y;
        S[x]=y;
        flag=N;
        while(x<N)
        {
            if(y<N)
            {
                FS(x,y,t1);
                FS(x+1,y,t2);
                FS(x+1,y-1,t3);
                if(t2!=max(t1+ch,t3)+arr[x+1][y])
                    S[++x]=y;
                else
                {
                    FS(x,y+1,t2);
                    FS(x-1,y+1,t3);
                    if(t2!=max(t1+ch,t3)+arr[x][y+1])
                        y++;
                    else
                    {
                        flag=x;
                        break;
                    }
                }
            }
            else
            {
                FS(x,N,t1);
                FS(x+1,N,t2);
                FS(x+1,N-1,t3);
                if(t2!=max(t1+ch,t3)+arr[x+1][y])
                    S[++x]=y;
                else
                {
                    flag=x;
                    break;
                }
            }
        }
        x=X;
        y=Y;
        while(x<=flag)
        {
            if(y<N)
            {
                FS(x,y,t1);
                FS(x,y+1,t2);
                FS(x-1,y+1,t3);
                if(t2!=max(t1+ch,t3)+arr[x][y+1])
                    y++;
                else
                {
                    E[x]=y;
                    if(y-1>=S[x+1])
                        x++;
                    else
                    {
                        FS(x+1,y,t2);
                        FS(x+1,y-1,t3);
                        if(t2!=max(t1+ch,t3)+arr[x+1][y])
                            x++;
                        else
                            break;
                    }
                }
            }
            else
            {
                E[x]=y;
                if(y-1>=S[x+1])
                    x++;
                else
                {
                    FS(x+1,y,t2);
                    FS(x+1,y-1,t3);
                    if(t2!=max(t1+ch,t3)+arr[x+1][y])
                        x++;
                    else
                        break;
                }
            }
        }
        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 Incorrect 5 ms 2552 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 222 ms 53788 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 54.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 2552 KB Output isn't correct
2 Halted 0 ms 0 KB -