제출 #805249

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
805249		serifefedartar	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	443 ms	37736 KiB

Main

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

#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define MOD 1000000007
#define LOGN 20
#define MAXN 200005

struct node {
    ll left, right;
    ll l0r0, l0r1, l1r0, l1r1;
};

node merge(node a, node b) {
    node temp;
    temp.left = a.left;
    temp.right = b.right;
    if (a.right * b.left < 0) {
        temp.l1r1 = max(abs(a.l1r0) + abs(b.l1r1), abs(a.l1r1) + abs(b.l0r1));
        temp.l1r0 = max(abs(a.l1r0) + abs(b.l1r0), abs(a.l1r1) + abs(b.l0r0));
        temp.l0r1 = max(abs(a.l0r0) + abs(b.l1r1), abs(a.l0r1) + abs(b.l0r1));
        temp.l0r0 = max(abs(a.l0r0) + abs(b.l1r0), abs(a.l0r1) + abs(b.l0r0));
    } else {
        temp.l1r1 = abs(a.l1r1) + abs(b.l1r1);
        temp.l1r0 = abs(a.l1r1) + abs(b.l1r0);
        temp.l0r1 = abs(a.l0r1) + abs(b.l1r1);
        temp.l0r0 = abs(a.l0r1) + abs(b.l1r0);
    }
    return temp;
}

vector<ll> arr, diff;
node sg[4*MAXN];
void init(int k, int a, int b) {
    if (a == b) {
        sg[k].left = sg[k].right = sg[k].l1r1 = diff[a];
        sg[k].l0r0 = sg[k].l0r1 = sg[k].l1r0 = 0;
        return ;
    }
    init(2*k, a, (a+b)/2);
    init(2*k+1, (a+b)/2+1, b);
    sg[k] = merge(sg[2*k], sg[2*k+1]);
}

void point_update(int k, int a, int b, int plc, ll val) {
    if (a > plc || b < plc)
        return ;
    if (a == b) {
        sg[k].left = sg[k].right += val;
        sg[k].l1r1 = abs(sg[k].right); 
        sg[k].l0r0 = sg[k].l0r1 = sg[k].l1r0 = 0;
        return ;   
    }
    point_update(2*k, a, (a+b)/2, plc, val);
    point_update(2*k+1, (a+b)/2+1, b, plc, val);
    sg[k] = merge(sg[2*k], sg[2*k+1]);
}

int main() {
    fast
    ll n, q;
    cin >> n >> q;

    arr = vector<ll>(n+1);
    diff = vector<ll>(n+1);
    for (int i = 1; i <= n; i++)
        cin >> arr[i];
    for (int i = 2; i <= n; i++)
        diff[i-1] = arr[i] - arr[i-1];
    init(1, 1, n-1);

    while (q--) {
        ll l, r, val;
        cin >> l >> r >> val;
        if (l != 1)
            point_update(1, 1, n-1, l-1, val);
        if (r != n)
            point_update(1, 1, n-1, r, -val);
        cout << sg[1].l1r1 << "\n";
    }
}

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