Submission #861732

#	Time	Username	Problem	Language	Result	Execution time	Memory
861732		dbence	Sjeckanje (COCI21_sjeckanje)	C++14	0 / 110	1 ms	4444 KiB

Main

#include <bits/stdc++.h>
#define l(x) (x << 1) + 1
#define r(x) (x << 1) + 2
using namespace std;
typedef long long ll;
const ll N = 2e5 + 1;
ll n, q, current, arr[N], dif[N], val[N];

void set_value(ll i, ll x) {
    current -= val[i]; val[i] = x;
    current += val[i];
}

void update(ll i, ll x) {
    dif[i] += x;
    if (i == 1) {
        set_value(i, abs(dif[i]));
        return;
    }
    if (1ll * dif[i - 1] * dif[i] >= 0) {
        set_value(i - 1, abs(dif[i - 1]));
        set_value(i, abs(dif[i]));
    } else if (abs(dif[i - 1]) > abs(dif[i])) {
        set_value(i - 1, abs(dif[i - 1]));
        set_value(i, 0);
    } else {
        set_value(i - 1, 0);
        set_value(i, abs(dif[i]));
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> q;
    for (ll i = 1; i <= n; ++i) {
        cin >> arr[i];
    }
    for (ll i = 1; i < n; ++i) {
        dif[i] = arr[i + 1] - arr[i];
    }
    for (ll i = 1; i < n; ++i) {
        update(i, 0);
    }
    for (ll i = 0; i < q; ++i) {
        ll l, r, x;
        cin >> l >> r >> x;
        if (l > 1) {
            update(l - 1, x);
        }
        if (r < n) {
            update(r, -x);
        }
        cout << current << "\n";
    }
}

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