Submission #1066105

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066105		sammyuri	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	692 ms	18260 KiB

foehn_phenomena

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

typedef long long ll;

const int MAXN = (1 << 18);
ll tree[2 * MAXN], lazy[2 * MAXN];
void init() {
    for (int i = 0; i < 2 * MAXN; i ++)
        tree[i] = lazy[i] = 0;
}
void pushdown(int index) {
    if (lazy[index] != 0) {
        if (index < MAXN) {
            lazy[2 * index] += lazy[index];
            lazy[2 * index + 1] += lazy[index];
            tree[index] = tree[2 * index] + tree[2 * index + 1] + lazy[index];
        } else {
            tree[index] += lazy[index];
        }
        lazy[index] = 0;
    }
}
void upd(int left, int right, int index, int maxl, int maxr, ll value) {
    if (left == maxl && right == maxr) {
        lazy[index] += value; return;
    }
    pushdown(index);
    int mid = (maxl + maxr) / 2;
    if (left <= mid)
        upd(left, min(mid, right), 2 * index, maxl, mid, value);
    if (right > mid)
        upd(max(mid + 1, left), right, 2 * index + 1, mid + 1, maxr, value);
}
ll query(int x, int index, int maxl, int maxr) {
    pushdown(index);
    if (x == maxl && x == maxr) {
        return tree[index];
    }
    int mid = (maxl + maxr) / 2;
    if (x <= mid)
        return query(x, 2 * index, maxl, mid);
    else
        return query(x, 2 * index + 1, mid + 1, maxr);
}
ll get(int x) {return query(x, 1, 0, MAXN - 1);}
ll s, t;
ll calc(ll a, ll b) {
    if (a < b)
        return (-s) * (b - a);
    else
        return t * (a - b);
}

int main() {
    init();
    int n, q;
    cin >> n >> q >> s >> t;
    ll curval = 0;
    ll last = 0;
    for (int i = 0; i <= n; i ++) {
        ll xx; cin >> xx;
        upd(i, i, 1, 0, MAXN - 1, xx);
        curval += calc(last, xx);
        last = xx;
    }
    for (int i = 0; i < q; i ++) {
        int l, r; cin >> l >> r;
        ll dx; cin >> dx;
        curval -= calc(get(l - 1), get(l));
        if (r != n)
            curval -= calc(get(r), get(r + 1));
        upd(l, r, 1, 0, MAXN - 1, dx);
        curval += calc(get(l - 1), get(l));
        if (r != n)
            curval += calc(get(r), get(r + 1));
        cout << curval << endl;
    }
}

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