Submission #789494

#	Time	Username	Problem	Language	Result	Execution time	Memory
789494		8pete8	Sjeckanje (COCI21_sjeckanje)	C++14	0 / 110	1 ms	340 KiB

Main

#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include<bitset>
#include<stack>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define pppiiii pair<pii,pii>
#define ppii pair<pii,pii>
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
const int mxn=2*1e5+1,mx=1e6;
#define int long long
struct node{
    int dp[2][2],l,r;
    // left right border
};
node seg[2*mxn+10];
int v[mxn+10],d[mxn+10];
int n,q;
node merg(node a,node b){
    node ans;
    if(a.l==INT_MAX)return b;
    else if(b.l==INT_MAX)return a;
    ans.l=a.l;
    ans.r=b.r;
    ans.dp[0][1]=max(a.dp[0][1]+b.dp[0][1],a.dp[0][0]+b.dp[1][1]);
    ans.dp[0][0]=max(a.dp[0][0]+b.dp[1][0],a.dp[0][1]+b.dp[0][0]);
    ans.dp[1][0]=max(a.dp[1][0]+b.dp[1][0],a.dp[1][1]+b.dp[0][0]);
    ans.dp[1][1]=max(a.dp[1][1]+b.dp[0][1],a.dp[1][0]+b.dp[1][1]);
    if((d[a.r]>=0&&d[b.l]>=0)||(d[a.r]<=0&&d[b.l]<=0)){
        ans.dp[0][1]=max(ans.dp[0][1],a.dp[0][1]+b.dp[1][1]);
        ans.dp[0][0]=max(ans.dp[0][0],a.dp[0][1]+b.dp[1][0]);
        ans.dp[1][0]=max(ans.dp[1][0],a.dp[1][1]+b.dp[1][0]);
        ans.dp[1][1]=max(ans.dp[1][1],a.dp[1][1]+b.dp[1][1]);
    }
    //0 take left/right
    return ans;
}
void init(node&a){a.l=a.r=INT_MAX;}
void up(int pos,int val){
    pos+=n;
    seg[pos].l=pos-n;
    seg[pos].r=pos-n;
    seg[pos].dp[1][1]=val;
    for(;pos>1;pos>>=1){
        node a=seg[pos],b=seg[pos^1];
        if(pos&1)swap(a,b);
        seg[pos>>1]=merg(a,b);
    }
}
int qry(int l,int r){
    node ansl,ansr;
    init(ansl);
    init(ansr);
    for(l+=n,r+=n;l<=r;l>>=r,r>>=1){
        if(l&1)ansl=merg(ansl,seg[l++]);
        if(!(r&1))ansr=merg(seg[r--],ansr);
    }
    ansl=merg(ansl,ansr);
    return max({ansl.dp[0][0],ansl.dp[0][1],ansl.dp[1][1],ansl.dp[1][0]});
}
int32_t main(){
    cin>>n>>q;
    for(int i=0;i<2*n;i++)init(seg[i]);
    for(int i=0;i<n;i++)cin>>v[i];
    n--;
    for(int i=0;i<n;i++)d[i]=v[i+1]-v[i];
    for(int i=0;i<n;i++)up(i,abs(d[i]));
    while(q--){
        int l,r,x;cin>>l>>r>>x;
        l--,r--;
        if(l)d[l-1]+=x;
        if(r<n)d[r]-=x;
        if(l)up(l-1,abs(d[l-1]));
        if(r<n)up(r,abs(d[r]));//2 0 2 2
        cout<<qry(0,n)<<'\n';
    }
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 40
• Subtask 3: 0 / 55