제출 #428953

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
428953		xyz	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	953 ms	33688 KiB

Main

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

const int N = 5e5 + 200;

ll t[4 * N][2][2];
bool sign[4 * N][2][2][2];

void umax(ll &a, bool& L, bool& R, ll val, bool& uL, bool& uR){
    if(val > a){
        a = val;
        L = uL;
        R = uR;
    }
}

void combine(int v, int l, int r){
    for(int x = 0; x <= 1; x ++){
        for(int y = 0; y <= 1; y ++){
            t[v][x][y] = -1;
            umax(t[v][x][y], sign[v][x][y][0], sign[v][x][y][1], abs(t[l][x][0]) + abs(t[r][0][y]), sign[l][x][0][0], sign[r][0][y][1]);
            umax(t[v][x][y], sign[v][x][y][0], sign[v][x][y][1], abs(t[l][x][1]) + abs(t[r][0][y]), sign[l][x][1][0], sign[r][0][y][1]);
            umax(t[v][x][y], sign[v][x][y][0], sign[v][x][y][1], abs(t[l][x][0]) + abs(t[r][1][y]), sign[l][x][0][0], sign[r][1][y][1]);
            if(sign[l][x][1][1] == sign[r][1][y][0])
                umax(t[v][x][y], sign[v][x][y][0], sign[v][x][y][1], abs(t[l][x][1]) + abs(t[r][1][y]), sign[l][x][1][0], sign[r][1][y][1]);
        }
    }
}

void modify(int v, int tl, int tr, int pos, ll x){
    if(tl == tr){
        t[v][1][1] += x;
        sign[v][1][1][0] = sign[v][1][1][1] = (t[v][1][1] >= 0);
        return;
    }
    int tm = (tl + tr) / 2;
    if(pos <= tm)
        modify(v * 2, tl, tm, pos, x);
    else
        modify(v * 2 + 1, tm + 1, tr, pos, x);
    combine(v, v * 2, v * 2 + 1);
}

int main(){
    ios_base :: sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, q;
    cin >> n >> q;
    vector<ll> a(n), d(n - 1);
    for(int i = 0; i < n; i ++)
        cin >> a[i];
    for(int i = 1; i < n; i ++)
        d[i - 1] = a[i - 1] - a[i];
    for(int i = 0; i < n - 1; i ++)
        modify(1, 0, n - 2, i, d[i]);
    while(q --){
        int l, r;
        ll x;
        cin >> l >> r >> x;
        if(l > 1)
            modify(1, 0, n - 2, l - 2, -x);
        if(r < n)
            modify(1, 0, n - 2, r - 1, x);
        cout << max(max(t[1][0][0], t[1][1][1]),
                    max(t[1][1][0], t[1][0][1])) << "\n";
    }
}

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