oj.uz

Submission #74472

# Submission time Handle Problem Language Result Execution time Memory
74472 2018-09-02T07:03:02 Z gs18115 None (KOI17_shell) C++14
46 / 100
 329 ms 155940 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]=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,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;
                    }
                }
            }
            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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2552 KB Output is correct
2 Correct 5 ms 2648 KB Output is correct
3 Correct 5 ms 2668 KB Output is correct
4 Correct 6 ms 2668 KB Output is correct
5 Correct 6 ms 2668 KB Output is correct
6 Correct 6 ms 2776 KB Output is correct
7 Correct 6 ms 2876 KB Output is correct
8 Correct 6 ms 2996 KB Output is correct
9 Correct 6 ms 2996 KB Output is correct
10 Correct 5 ms 2996 KB Output is correct

Subtask #2
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 53984 KB Output is correct
2 Correct 238 ms 58616 KB Output is correct
3 Correct 233 ms 62976 KB Output is correct
4 Correct 219 ms 67308 KB Output is correct
5 Correct 219 ms 71780 KB Output is correct
6 Correct 219 ms 76276 KB Output is correct
7 Correct 215 ms 80624 KB Output is correct
8 Correct 211 ms 85064 KB Output is correct
9 Correct 216 ms 89484 KB Output is correct
10 Correct 212 ms 93964 KB Output is correct

Subtask #3
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2552 KB Output is correct
2 Correct 5 ms 2648 KB Output is correct
3 Correct 5 ms 2668 KB Output is correct
4 Correct 6 ms 2668 KB Output is correct
5 Correct 6 ms 2668 KB Output is correct
6 Correct 6 ms 2776 KB Output is correct
7 Correct 6 ms 2876 KB Output is correct
8 Correct 6 ms 2996 KB Output is correct
9 Correct 6 ms 2996 KB Output is correct
10 Correct 227 ms 53984 KB Output is correct
11 Correct 238 ms 58616 KB Output is correct
12 Correct 233 ms 62976 KB Output is correct
13 Correct 219 ms 67308 KB Output is correct
14 Correct 219 ms 71780 KB Output is correct
15 Correct 219 ms 76276 KB Output is correct
16 Correct 215 ms 80624 KB Output is correct
17 Correct 211 ms 85064 KB Output is correct
18 Correct 216 ms 89484 KB Output is correct
19 Correct 212 ms 93964 KB Output is correct
20 Runtime error 329 ms 155940 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Halted 0 ms 0 KB -