Submission #140524

#	Time	Username	Problem	Language	Result	Execution time	Memory
140524		meatrow	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	486 ms	15868 KiB

foehn_phenomena

//#pragma GCC optimize("O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
//#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;

const int N = 2e5;

ll t[N * 4];
ll a[N];

void build(ll a[], int v, int tl, int tr) {
    if (tl == tr) {
        t[v] = a[tl];
    } else {
        int tm = (tl + tr) / 2;
        build(a, v*2, tl, tm);
        build(a, v*2+1, tm+1, tr);
        t[v] = 0;
    }
}

void update(int v, int tl, int tr, int l, int r, int add) {
    if (l > r)
        return;
    if (l == tl && r == tr) {
        t[v] += add;
    } else {
        int tm = (tl + tr) / 2;
        update(v*2, tl, tm, l, min(r, tm), add);
        update(v*2+1, tm+1, tr, max(l, tm+1), r, add);
    }
}

ll get(int v, int tl, int tr, int pos) {
    if (tl == tr)
        return t[v];
    int tm = (tl + tr) / 2;
    if (pos <= tm)
        return t[v] + get(v*2, tl, tm, pos);
    else
        return t[v] + get(v*2+1, tm+1, tr, pos);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, q, s, t;
    cin >> n >> q >> s >> t;
    n++;
    ll down = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (i) {
            if (a[i] < a[i - 1]) {
                down -= a[i] - a[i - 1];
            }
        } 
    }
    build(a, 1, 0, n - 1);
    while (q--) {
        int l, r, x;
        cin >> l >> r >> x;
        ll a1 = get(1, 0, n - 1, l - 1);
        ll b1 = get(1, 0, n - 1, l);
        ll a2 = get(1, 0, n - 1, r);
        ll b2 = get(1, 0, n - 1, r + 1);
        if (b1 < a1) {
            down += b1 - a1;
        }
        if (r + 1 < n && b2 < a2) {
            down += b2 - a2;
        }
        update(1, 0, n - 1, l, r, x);
        a1 = get(1, 0, n - 1, l - 1);
        b1 = get(1, 0, n - 1, l);
        a2 = get(1, 0, n - 1, r);
        b2 = get(1, 0, n - 1, r + 1);
        if (b1 < a1) {
            down -= b1 - a1;
        }
        if (r + 1 < n && b2 < a2) {
            down -= b2 - a2;
        }
        cout << t * down - s * (get(1, 0, n - 1, n - 1) + down) << '\n';

    }
    return 0;
}

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