답안 #643628

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
643628 2022-09-22T16:37:29 Z Augustyn Sjeckanje (COCI21_sjeckanje) C++14
0 / 110
1 ms 340 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];
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][0]);
    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];
    }
    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;
        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];
        }
        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]=INT_MIN;
    }
    for(int i=pod-1;i;--i)
    {
        akttutaj(i);
    }

    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:119:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |     scanf("%d%d",&n,&q);
      |     ~~~~~^~~~~~~~~~~~~~
Main.cpp:124:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |         scanf("%lld",&ciag[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:142:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |         scanf("%d%d%lld",&l,&r,&xi);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -