#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;
const int N=2e5+1;
int v[N],a[N],n,m;
int dp[4*N][2][2],lazy[4*N];//practic intervalu nostru are capete sau n-are capete
int borders[4*N][2];//0 e left 1 e right
void merge(int nod_a,int nod_b,int nod_c)//vrem sa dam merge la nod_a si nod_b in nod_c
{
borders[nod_c][0]=borders[nod_a][0];
borders[nod_c][1]=borders[nod_b][1];
dp[nod_c][0][0]=0;
dp[nod_c][0][1]=0;
dp[nod_c][1][0]=0;
dp[nod_c][1][1]=0;
for(int k=0; k<2; k++)
{
for(int d=0; d<2; d++)
{
for(int mid=0; mid<2; mid++)
{
for(int mid2=0; mid2<2; mid2++)
{
if(mid&&mid2)
{
if((borders[nod_a][1]>=0)==(borders[nod_b][0]>=0))
{
dp[nod_c][k][d]=max(dp[nod_c][k][d],dp[nod_a][k][mid]+dp[nod_b][mid2][d]);
}
}
else
{
dp[nod_c][k][d]=max(dp[nod_c][k][d],dp[nod_a][k][mid]+dp[nod_b][mid2][d]);
}
}
}
}
}
}
void update(int nod,int st,int dr,int poz,int val)
{
if(st==dr)
{
borders[nod][0]+=val;
borders[nod][1]+=val;
dp[nod][1][1]=abs(borders[nod][0]);
dp[nod][0][0]=0;
dp[nod][1][0]=0;
dp[nod][0][1]=0;
}
else
{
int mij=(st+dr)/2;
if(poz<=mij)
{
update(nod*2,st,mij,poz,val);
}
else
{
update(nod*2+1,mij+1,dr,poz,val);
}
merge(nod*2,nod*2+1,nod);
}
}
void read()
{
cin>>n>>m;
for(int i=1; i<=n; i++)
{
cin>>v[i];
}
for(int i=1; i<=n-1; i++)
{
a[i]=v[i+1]-v[i];
}
for(int i=1; i<=n-1; i++)
{
update(1,1,n,i,a[i]);
}
}
void solve()
{
for(int i=1; i<=m; i++)
{
int l,r,x;
cin>>l>>r>>x;
if(l-1>=1)
{
update(1,1,n,l-1,x);
}
if(r<n)
{
update(1,1,n,r,-x);
}
cout<<dp[1][1][1]<<'\n';
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
read();
solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4432 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4432 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4432 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
