oj.uz

Submission #643653

# Submission time Handle Problem Language Result Execution time Memory
643653 2022-09-22T17:41:35 Z Augustyn Sjeckanje (COCI21_sjeckanje) C++14
110 / 110
 588 ms 42488 KB 
#include<bits/stdc++.h>
using namespace std;
int n,q,pod=1;
long long drze[524288][10];
long long ciag[200001];
bool start;
long long zbodp[3];
long long minniesk=-100000000000000;
void akttutaj(int i)
{
    drze[i][0]=drze[i*2][0]+drze[i*2+1][0];
    drze[i][0]=max(drze[i][0],drze[i*2][1]+drze[i*2+1][4]);
    drze[i][0]=max(drze[i][0],drze[i*2][2]+drze[i*2+1][3]);

    drze[i][1]=drze[i*2][1];
    drze[i][1]=max(drze[i][1],drze[i*2][0]+drze[i*2+1][1]);
    drze[i][1]=max(drze[i][1],drze[i*2][2]+drze[i*2+1][5]);
    drze[i][1]=max(drze[i][1],drze[i*2][1]+drze[i*2+1][6]);

    drze[i][2]=drze[i*2][2];
    drze[i][2]=max(drze[i][2],drze[i*2][0]+drze[i*2+1][2]);
    drze[i][2]=max(drze[i][2],drze[i*2][2]+drze[i*2+1][7]);
    drze[i][2]=max(drze[i][2],drze[i*2][1]+drze[i*2+1][8]);

    drze[i][3]=drze[i*2+1][3];
    drze[i][3]=max(drze[i][3],drze[i*2][3]+drze[i*2+1][0]);
    drze[i][3]=max(drze[i][3],drze[i*2][5]+drze[i*2+1][4]);
    drze[i][3]=max(drze[i][3],drze[i*2][7]+drze[i*2+1][3]);

    drze[i][4]=drze[i*2+1][4];
    drze[i][4]=max(drze[i][4],drze[i*2][4]+drze[i*2+1][0]);
    drze[i][4]=max(drze[i][4],drze[i*2][6]+drze[i*2+1][4]);
    drze[i][4]=max(drze[i][4],drze[i*2][8]+drze[i*2+1][3]);

    drze[i][5]=max(drze[i*2][5],drze[i*2+1][5]);
    drze[i][5]=max(drze[i][5],drze[i*2][3]+drze[i*2+1][1]);
    drze[i][5]=max(drze[i][5],drze[i*2][5]+drze[i*2+1][6]);
    drze[i][5]=max(drze[i][5],drze[i*2][7]+drze[i*2+1][5]);

    drze[i][6]=max(drze[i*2][6],drze[i*2+1][6]);
    drze[i][6]=max(drze[i][6],drze[i*2][4]+drze[i*2+1][1]);
    drze[i][6]=max(drze[i][6],drze[i*2][6]+drze[i*2+1][6]);
    drze[i][6]=max(drze[i][6],drze[i*2][8]+drze[i*2+1][5]);

    drze[i][7]=max(drze[i*2][7],drze[i*2+1][7]);
    drze[i][7]=max(drze[i][7],drze[i*2][3]+drze[i*2+1][2]);
    drze[i][7]=max(drze[i][7],drze[i*2][5]+drze[i*2+1][8]);
    drze[i][7]=max(drze[i][7],drze[i*2][7]+drze[i*2+1][7]);

    drze[i][8]=max(drze[i*2][8],drze[i*2+1][8]);
    drze[i][8]=max(drze[i][8],drze[i*2][4]+drze[i*2+1][2]);
    drze[i][8]=max(drze[i][8],drze[i*2][6]+drze[i*2+1][8]);
    drze[i][8]=max(drze[i][8],drze[i*2][8]+drze[i*2+1][7]);
}
void przep(int ter)
{
    for(int i=0;i<=1;++i)
    {
        drze[(ter<<1)^i][1]+=drze[ter][9];
        drze[(ter<<1)^i][3]+=drze[ter][9];
        drze[(ter<<1)^i][5]+=drze[ter][9]+drze[ter][9];
        drze[(ter<<1)^i][2]-=drze[ter][9];
        drze[(ter<<1)^i][4]-=drze[ter][9];
        drze[(ter<<1)^i][8]-=(drze[ter][9]+drze[ter][9]);
        drze[(ter<<1)^i][9]+=drze[ter][9];
        if(ter*2>=pod)
        {
            drze[ter<<1][8]=minniesk;
            drze[ter<<1][5]=minniesk;
            drze[(ter<<1)^1][8]=minniesk;
            drze[(ter<<1)^1][5]=minniesk;
        }
    }
    drze[ter][9]=0;
}
void aktu_drze(int ter,int pocz,int kon,int odtego,int dotego,int ile)
{
    if(pocz>=odtego&&kon<=dotego)
    {
        drze[ter][1]+=ile;
        drze[ter][3]+=ile;
        drze[ter][5]+=ile+ile;
        drze[ter][2]-=ile;
        drze[ter][4]-=ile;
        drze[ter][8]-=(ile+ile);
        drze[ter][9]+=ile;
        if(ter>=pod)
        {
            drze[ter][8]=minniesk;
            drze[ter][5]=minniesk;
        }
        return;
    }
    przep(ter);
    if((pocz+kon)/2>=odtego)
        aktu_drze(ter<<1,pocz,(pocz+kon)/2,odtego,dotego,ile);
    if((pocz+kon)/2+1<=dotego)
        aktu_drze((ter<<1)^1,(pocz+kon)/2+1,kon,odtego,dotego,ile);
    akttutaj(ter);
}
void zbierz_odp(int ter,int pocz,int kon,int odtego,int dotego)
{
    if(pocz>=odtego&&kon<=dotego)
    {
        if(start)
        {
            zbodp[0]=drze[ter][1];
            zbodp[1]=drze[ter][2];
            zbodp[2]=drze[ter][0];
            start=0;
        }
        else
        {
            long long nzbodp[3];
            nzbodp[0]=max(zbodp[0]+drze[ter][6],max(zbodp[1]+drze[ter][5],zbodp[2]+drze[ter][1]));
            nzbodp[1]=max(zbodp[0]+drze[ter][8],max(zbodp[1]+drze[ter][7],zbodp[2]+drze[ter][2]));
            nzbodp[2]=max(zbodp[0]+drze[ter][4],max(zbodp[1]+drze[ter][3],zbodp[2]+drze[ter][0]));
            for(int i=0;i<3;++i)
                zbodp[i]=nzbodp[i];
        }
       // cout<<ter<<" "<<kon-pod<<" "<<zbodp[0]<<" "<<zbodp[1]<<" "<<zbodp[2]<<" "<<drze[ter][0]<<endl;
        return;
    }
    przep(ter);
    if((pocz+kon)/2>=odtego)
        zbierz_odp(ter<<1,pocz,(pocz+kon)/2,odtego,dotego);
    if((pocz+kon)/2+1<=dotego)
        zbierz_odp((ter<<1)^1,(pocz+kon)/2+1,kon,odtego,dotego);
    akttutaj(ter);
}
int main()
{
    scanf("%d%d",&n,&q);
    while(pod<n)
        pod<<=1;
    for(int i=0;i<n;++i)
    {
        scanf("%lld",&ciag[i]);
        drze[pod+i][1]=ciag[i];
        drze[pod+i][2]=-ciag[i];
        drze[pod+i][3]=ciag[i];
        drze[pod+i][4]=-ciag[i];
        for(int j=5;j<=8;++j)
            drze[pod+i][j]=minniesk;
    }
    for(int i=pod-1;i;--i)
    {
        akttutaj(i);
    }
    // cout<<8<<" "<<drze[8][0]<<" "<<drze[8][1]<<" "<<drze[8][2]<<" "<<drze[8][3]<<" "<<drze[8][4]<<endl;
    // cout<<9<<" "<<drze[9][0]<<" "<<drze[9][1]<<" "<<drze[9][2]<<" "<<drze[9][3]<<" "<<drze[9][4]<<endl;
    // start=1;
    //     zbierz_odp(1,pod,pod+pod-1,pod,n-1+pod);
    //     printf("%lld\n",zbodp[2]);
    //     return 0;
    while(q)
    {
        --q;
        int l,r;
        long long xi;
        scanf("%d%d%lld",&l,&r,&xi);
        --l;
        --r;
        aktu_drze(1,pod,pod+pod-1,l+pod,r+pod,xi);
        start=1;
        zbierz_odp(1,pod,pod+pod-1,pod,n-1+pod);
        printf("%lld\n",zbodp[2]);
    }
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:133:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |     scanf("%d%d",&n,&q);
      |     ~~~~~^~~~~~~~~~~~~~
Main.cpp:138:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  138 |         scanf("%lld",&ciag[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:161:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  161 |         scanf("%d%d%lld",&l,&r,&xi);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 5 ms 1016 KB Output is correct
8 Correct 6 ms 980 KB Output is correct
9 Correct 5 ms 980 KB Output is correct
10 Correct 8 ms 976 KB Output is correct
11 Correct 6 ms 980 KB Output is correct
12 Correct 8 ms 1016 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 5 ms 1016 KB Output is correct
8 Correct 6 ms 980 KB Output is correct
9 Correct 5 ms 980 KB Output is correct
10 Correct 8 ms 976 KB Output is correct
11 Correct 6 ms 980 KB Output is correct
12 Correct 8 ms 1016 KB Output is correct
13 Correct 588 ms 42328 KB Output is correct
14 Correct 545 ms 42484 KB Output is correct
15 Correct 545 ms 42484 KB Output is correct
16 Correct 534 ms 42372 KB Output is correct
17 Correct 547 ms 42384 KB Output is correct
18 Correct 553 ms 42488 KB Output is correct