#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);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
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 |
| # |
결과 |
실행 시간 |
메모리 |
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 |
| # |
결과 |
실행 시간 |
메모리 |
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 |
