Submission #751260

#	Time	Username	Problem	Language	Result	Execution time	Memory
751260		aufan	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	133 ms	7284 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;

int32_t main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        int n, q, s, t;
        cin >> n >> q >> s >> t;
        vector<int> zx(n+5);
        for (int i = 0; i <= n; i++) cin >> zx[i];
        vector<int> fen(n+5, 0);
        auto add = [&](int x, int val) {
                for (;x<=n;x+=x&-x) fen[x] += val;
        };
        auto get = [&](int x) {
                int res = 0;
                for (;x>0;x-=x&-x) res += fen[x];
                return res;
        };
        for (int i = 1; i <= n; i++) {
                add(i, zx[i]);
                add(i+1, -zx[i]);
        }
        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] = get(l-1);
                zx[l] = get(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] = get(r);
                        zx[r+1] = get(r+1);
                        if (zx[r] < zx[r+1]) {
                                ans += s*(zx[r+1] - zx[r]);
                        } else {
                                ans -= t*(zx[r] - zx[r+1]);
                        }
                }
                add(l, x);
                add(r+1, -x);
                zx[l] += x;
                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