Submission #1292641

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292641		fairkrash	Foehn Phenomena (JOI17_foehn_phenomena)	C++20	100 / 100	284 ms	18460 KiB

foehn_phenomena

#include <bits/stdc++.h>

#include <random>

using namespace std;
using ll = long long;
using ld = long double;

ll INF = 1e18;

vector<pair<ll, ll>> tree;
vector<ll> z;

void build(ll v, ll vl, ll vr) {
    if (vr - vl == 1) {
        if (z[vl] < 0) {
            tree[v].second = z[vl];
        } else {
            tree[v].first = z[vl];
        }
        return;
    }
    ll mid = (vr + vl) / 2;
    build(v * 2, vl, mid);
    build(v * 2 + 1, mid, vr);
    tree[v].second = tree[v * 2].second + tree[v * 2 + 1].second;
    tree[v].first = tree[v * 2].first + tree[v * 2 + 1].first;
}


void change(ll v, ll vl, ll vr, ll ind, ll x) {
    if (vr - vl == 1) {
        z[vl] += x;
        tree[v].second = 0;
        tree[v].first = 0;
        if (z[vl] < 0) {
            tree[v].second = z[vl];
        } else {
            tree[v].first = z[vl];
        }
        return;
    }
    ll mid = (vr + vl) / 2;
    if (ind < mid) {
        change(v * 2, vl, mid, ind, x);
    } else {
        change(v * 2 + 1, mid, vr, ind, x);
    }
    tree[v].second = tree[v * 2].second + tree[v * 2 + 1].second;
    tree[v].first = tree[v * 2].first + tree[v * 2 + 1].first;
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll n, q, s, t;
    cin >> n >> q >> s >> t;
    ll a;
    cin >> a;
    for (ll i = 1; i < n + 1; i++) {
        ll b;
        cin >> b;
        z.push_back({b - a});
        a = b;
    }
    tree.assign(n * 4, {});
    build(1, 0, n);
    for (ll i = 0; i < q; i++) {
        ll v1, v2, v3;
        cin >> v1 >> v2 >> v3;
        change(1, 0, n, v1 - 1, v3);
        if (n != v2) {
            change(1, 0, n, v2, -v3);
        }
        cout << -tree[1].first * s - tree[1].second * t << endl;
    }
}

• Subtask 1: 30 / 30
• Subtask 2: 10 / 10
• Subtask 3: 60 / 60