Submission #643653

#	Time	Username	Problem	Language	Result	Execution time	Memory
643653		Augustyn	Sjeckanje (COCI21_sjeckanje)	C++14	110 / 110	588 ms	42488 KiB

Main

#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 (stderr)

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 / 15
• Subtask 2: 40 / 40
• Subtask 3: 55 / 55