#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);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
