Submission #1316092

#TimeUsernameProblemLanguageResultExecution timeMemory
1316092pobeFoehn Phenomena (JOI17_foehn_phenomena)C++20
100 / 100
214 ms30856 KiB
#include <bits/stdc++.h>
#define int long long
using namespace std;
ostream &operator <<(ostream &out, vector <int> val) {
    for (auto v : val) {
        out << v  << ' ';
    }
    return out;
}
struct node {
    int front = 0, back = 0, ans = 0, d = 0;
};

struct segment_tree {
    vector <node> tree;
    int n;
    int s, t;
    node merge(node a, node b) {
        node c;
        c.front = a.front;
        c.back = b.back;
        c.ans = a.ans + b.ans +  abs(a.back - b.front) * (a.back < b.front ? - s : t);
        return c;
    }
    void apply(int num, int v) {
        tree[num].front += v;
        tree[num].back += v;
        tree[num].d += v;
    }
    void push(int num) {
        if (tree[num].d != 0) {
            apply(2 * num + 1, tree[num].d);
            apply(2 * num + 2, tree[num].d);
            tree[num].d = 0;
        }
    }
    void upt(int num, int l, int r, int low, int high, int v) {
        if (l >= low && r <= high) {
            apply(num, v);
            return;
        }
        int med = (l + r) / 2;
        push(num);
        if (med > low) {
            upt(2 * num + 1, l, med, low, high, v);
        }
        if (med < high) {
            upt(2 * num + 2, med, r, low, high, v);
        }
        tree[num] = merge(tree[2 * num + 1], tree[2 * num + 2]);
    }
    void build(int num, int l, int r, vector <int> &val) {
        if (l == r - 1) {
            tree[num].back = val[l];
            tree[num].front = val[l];
            tree[num].d = 0;
            tree[num].ans = 0;
            return;
        }
        int med = (l + r) / 2;
        build(2 * num + 1, l, med, val);
        build(2 * num + 2, med, r, val);
        tree[num] = merge(tree[2 * num + 1], tree[2 * num + 2]);
    }
public:
    void init(int nn, int ns, int nt, vector <int> &val) {
        n = nn;
        s = ns;
        t = nt;
        tree.resize(4 * n);
        build(0, 0, n, val);
    }
    int get() {
        return tree[0].ans;
    }
    void upt(int l, int r, int v) {
        upt(0, 0, n, l, r, v);
    }
};

void solve() {
    int n, q, s, t;
    cin >> n >> q >> s >> t;
    vector <int> val(n + 1);
    for (auto &v : val) {
        cin >> v;
    }
    ++n;
    segment_tree now;
    now.init(n, s, t, val);
    for (int i = 0; i < q; ++i) {
        int l, r, v;
        cin >> l >> r >> v;
        now.upt(l, r + 1, v);
        cout << now.get() << '\n';
    }
}
signed main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int t = 1;
    solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...