이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct node{
int borders[2] , dp[2][2];
}seg[800001];
node combine(node a ,node b){
node res;
res.borders[0] = a.borders[0];
res.borders[1] = b.borders[1];
for(int i = 0;i<2;i++)for(int j = 0;j<2;j++)res.dp[i][j] = 0;
for(int l = 0;l<2;l++){
for(int m = 0;m<2;m++){
for(int o = 0;o<2;o++){
for(int r = 0;r<2;r++){
if(m&o){
if((a.borders[1]<0)==(b.borders[0]<0)){
res.dp[l][r] = max(res.dp[l][r],a.dp[l][m]+b.dp[o][r]);
}
}else{
res.dp[l][r] = max(res.dp[l][r],a.dp[l][m]+b.dp[o][r]);
}
}
}
}
}
return res;
}
int arr[200001];
void build(int p,int l,int r){
if(l==r){
seg[p].borders[0] = seg[p].borders[1] = arr[l];
seg[p].dp[0][0] = 0;
seg[p].dp[0][1] = 0;
seg[p].dp[1][0] = 0;
seg[p].dp[1][1] = abs(arr[l]);
return ;
}
int md = (l+r)/2;
build(p*2,l,md);
build(p*2+1,md+1,r);
seg[p] = combine(seg[p*2],seg[p*2+1]);
}
void update(int p,int l,int r,int idx){
if(l==r){
seg[p].borders[0] = seg[p].borders[1] = arr[l];
seg[p].dp[0][0] = 0;
seg[p].dp[0][1] = 0;
seg[p].dp[1][0] = 0;
seg[p].dp[1][1] = abs(arr[l]);
return ;
}
int md = (l+r)/2;
if(idx<=md)update(p*2,l,md,idx);
else update(p*2+1,md+1,r,idx);
seg[p] = combine(seg[p*2],seg[p*2+1]);
}
signed main(){
ios_base::sync_with_stdio(false);cin.tie(0);
int n,q;
cin>>n>>q;
int vl[n+1];
for(int i = 1;i<=n;i++)cin>>vl[i];
for(int i = 1;i<n;i++){
arr[i] = vl[i+1]-vl[i];
}
build(1,1,n-1);
while(q--){
int l,r,x;cin>>l>>r>>x;
if(l>1){
arr[l-1]+=x;
update(1,1,n-1,l-1);
}if(r<n){
arr[r]-=x;
update(1,1,n-1,r);
}
cout<<max({seg[1].dp[0][0],seg[1].dp[1][0],seg[1].dp[0][1],seg[1].dp[1][1]})<<endl;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |