Submission #866731

#	Time	Username	Problem	Language	Result	Execution time	Memory
866731		hqminhuwu	Sjeckanje (COCI21_sjeckanje)	C++14	55 / 110	362 ms	40912 KiB

Main

#include <bits/stdc++.h>
#define forr(_a,_b,_c) for(_a = (_b); _a <= (_c); ++_a)
#define ford(_a,_b,_c) for(_a = (_b) + 1; _a --> (_c);)
#define forf(_a,_b,_c) for(_a = (_b); _a < (_c); ++_a)
#define st first
#define nd second
#define ll long long
#define ull unsigned long long
#define pii pair <int,int>
#define pll pair <ll,ll>
#define piii pair <int,pii>
#define vi vector <int>
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define file "test"


using namespace std;
const int N = 5e5 + 5;
const ll oo = 1e16;
const ll mod = 1e9 + 7;

struct node {
    ll l,r,uu,vv,uv,vu;
    node operator + (node a){
        node k;
        k.uu = max (uu + a.uu,max (uv + a.uu,max(uu + a.vu,uv + a.vu)));
        k.vv = max (vu + a.uv,max (vv + a.uv,max(vu + a.vv,vv + a.vv)));
        k.uv = max (uu + a.uv,max (uv + a.uv,max(uu + a.vv,uv + a.vv)));
        k.vu = max (vu + a.uu,max (vv + a.uu,max(vu + a.vu,vv + a.vu)));
        if (r <= a.l){
            k.uu = max (k.uu,uu + a.uu + a.l - r);
            k.vv = max (k.vv,vu + a.uv + a.l - r);
            k.uv = max (k.uv,uu + a.uv + a.l - r);
            k.vu = max (k.vu,vu + a.uu + a.l - r);
        }
        else {
            k.uu = max (k.uu,uv + a.vu - a.l + r);
            k.vv = max (k.vv,vv + a.vv - a.l + r);
            k.uv = max (k.uv,uv + a.vv - a.l + r);
            k.vu = max (k.vu,vv + a.vu - a.l + r);
        }
        k.uv = max (0ll,k.uv);
        k.vu = max (0ll,k.vu);
        k.l = l;
        k.r = a.r;
        return k;
    }
};

node tree[4 * N];
ll lazy[N],a[N];

void down (int i){
    if (lazy[i] == 0) return;
    lazy[(i << 1)] += lazy[i];
    lazy[(i << 1) | 1] += lazy[i];
    tree[(i << 1)].l += lazy[i];
    tree[(i << 1)].r += lazy[i];
    tree[(i << 1) | 1].l += lazy[i];
    tree[(i << 1) | 1].r += lazy[i];
    lazy[i] = 0;
}
void build (int i, int l, int r){
    if (l == r){
        tree[i] = {a[l],a[l],0,0,-oo,-oo}; 
        return;
    }
    int mid = (l + r) >> 1;
    build ((i << 1), l, mid);
    build ((i << 1) | 1, mid + 1, r);
    tree[i] = (tree[(i << 1)] + tree[(i << 1) | 1]);
    // cout << l << " " << r << " " << tree[i].l << " " << tree[i].r << " " << tree[i].uu << " " << tree[i].vv 
    // << " " << tree[i].uv << " " << tree[i].vu << "\n";
}
void update (int i, int l, int r, int u, int v, ll val){
    if (l > v || r < u)
        return;
    if (l >= u && r <= v){
        tree[i].l += val;
        tree[i].r += val;
        lazy[i] += val;
        return;
    }
    down(i);
    int mid = (l + r) >> 1;
    update((i << 1),l,mid,u,v,val);
    update((i << 1) | 1, mid + 1,r,u,v,val);
    tree[i] = (tree[(i << 1)] + tree[(i << 1) | 1]);
}
int n,i,q,j,k;
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> q;
    forr (i,1,n)
        cin >> a[i];
    build(1,1,n);
    // ll tmp1 = max (tree[1].uu,tree[1].vv);
    //     ll tmp2 = max (tree[1].uv,tree[1].vu);
    //     cout << max (tmp1,tmp2) << "\n";
    while (q--){
        cin >> i >> j >> k;
        update(1,1,n,i,j,k);
        ll tmp1 = max (tree[1].uu,tree[1].vv);
        ll tmp2 = max (tree[1].uv,tree[1].vu);
        cout << max (tmp1,tmp2) << "\n";
    }
    return 0;
}
/*



*/

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