제출 #981790

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
981790		a_l_i_r_e_z_a	Sjeckanje (COCI21_sjeckanje)	C++14	110 / 110	265 ms	29008 KiB

Main

// In the name of God
// Hope is last to die

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC optimize("avx2")

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define pb push_back
// #define int long long
#define S second
#define F first
#define mp make_pair
#define smax(xyxy, yxy) (xyxy) = max((xyxy), (yxy))
#define smin(xyxy, yxy) (xyxy) = min((xyxy), (yxy))
#define all(xyxy) (xyxy).begin(), (xyxy).end()
#define len(xyxy) ((int)(xyxy).size())

const int maxn = 2e5 + 5;
const int inf = 1e9 + 7;
int n, q, a[maxn];
struct D{
    ll ans = 0, a = 0, b = 0, dpl = 0, dpr = 0, dplr = 0;
} node[maxn * 4];

D merge(D l, D r){
    bool u = (l.b >= 0), v = (r.a >= 0);
    D res;
    res.a = l.a;
    res.b = r.b;
    if(u == v){
        res.ans = l.ans + r.ans;
        res.dpl = l.dpl + r.ans;
        res.dpr = r.dpr + l.ans;
        res.dplr = l.dpl + r.dpr;
    }
    else{
        res.ans = max(l.ans + r.dpl, l.dpr + r.ans);
        res.dpl = max(l.dpl + r.dpl, l.dplr + r.ans);
        res.dpr = max(r.dpr + l.dpr, l.ans + r.dplr);
        res.dplr = max(l.dpl + r.dplr, l.dplr + r.dpr);
    }
    return res;
}

void build(int l = 0, int r = n, int id = 1){
    if(l == r - 1){
        int x = a[r] - a[l];
        node[id].ans = abs(x);
        node[id].a = node[id].b = x;
        node[id].dpl = node[id].dpr = node[id].dplr = 0;
        return;
    }
    int mid = (l + r) / 2;
    build(l, mid, id * 2);
    build(mid, r, id * 2 + 1);
    node[id] = merge(node[id * 2], node[id * 2 + 1]);
}

void upd(int p, int x, int l = 0, int r = n, int id = 1){
    if(l == r - 1){
        node[id].a = node[id].b = node[id].a + x;
        node[id].ans = abs(node[id].a);
        return;
    }
    int mid = (l + r) / 2;
    if(p < mid) upd(p, x, l, mid, id * 2);
    else upd(p, x, mid, r, id * 2 + 1);
    node[id] = merge(node[id * 2], node[id * 2 + 1]);
}

int32_t main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n >> q;
    for(int i = 0; i < n; i++) cin >> a[i];
    n--;
    build();
    while(q--){
        int l, r, x; cin >> l >> r >> x;
        l--, r--;
        if(l) upd(l - 1, x);
        if(r < n) upd(r, -x);
        cout << node[1].ans << '\n';
    }

    return 0;
}

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