Submission #751259

#	Time	Username	Problem	Language	Result	Execution time	Memory
751259		aufan	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	592 ms	30996 KiB

foehn_phenomena

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()

using namespace std;
vector<int> zx(222222);
struct node {
        int lz, val;
        int st, en;
        node *left, *right;
        void build(int start, int end) {
                st = start;
                en = end;
                if (st == en) {
                        val = zx[st];
                        return;
                }
                int md = (st + en)/2;
                left = new node();
                right = new node();
                left->build(st, md);
                right->build(md + 1, en);
        }
        void lazy() {
                left->val += lz;
                left->lz += lz;
                right->val += lz;
                right->lz += lz;
                lz = 0;
        }
        int query(int idx) {
                if (st > idx || en < idx) return 0ll;
                if (st == en) return val;
                lazy();
                return left->query(idx) + right->query(idx);
        }
        void update(int lf, int rg, int x) {
                if (st > rg || en < lf ) return;
                if (lf <= st && en <= rg) {
                        lz += x;
                        val += x;
                        return;
                }
                lazy();
                left->update(lf, rg, x);
                right->update(lf, rg, x);
        }
} sg;
int32_t main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        int n, q, s, t;
        cin >> n >> q >> s >> t;
        for (int i = 0; i <= n; i++) cin >> zx[i];
        sg.build(0, n);
        int ans = 0;
        for (int i = 0; i < n; i++) {
                if (zx[i] < zx[i+1]) {
                        ans -= s*(zx[i+1] - zx[i]);
                } else {
                        ans += t*(zx[i] - zx[i+1]);
                }
        }
        while (q --> 0) {
                int l, r, x;
                cin >> l >> r >> x;
                zx[l-1] = sg.query(l-1);
                zx[l] = sg.query(l);
                if (zx[l-1] < zx[l]) {
                        ans += s*(zx[l] - zx[l-1]);
                } else {
                        ans -= t*(zx[l-1] - zx[l]);
                }
                if (r < n) {
                        zx[r] = sg.query(r);
                        zx[r+1] = sg.query(r+1);
                        if (zx[r] < zx[r+1]) {
                                ans += s*(zx[r+1] - zx[r]);
                        } else {
                                ans -= t*(zx[r] - zx[r+1]);
                        }
                }
                sg.update(l, r, x);
                zx[l] += x;
                assert(zx[l] == sg.query(l));
                if (zx[l-1] < zx[l]) {
                        ans -= s*(zx[l] - zx[l-1]);
                } else {
                        ans += t*(zx[l-1] - zx[l]);
                }
                if (r < n) {
                        if (l != r) zx[r] += x;
                        if (zx[r] < zx[r+1]) {
                                ans -= s*(zx[r+1] - zx[r]);
                        } else {
                                ans += t*(zx[r] - zx[r+1]);
                        }
                }
                cout << ans << '\n';
        }
        return 0;
}

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