Submission #1338246

#TimeUsernameProblemLanguageResultExecution timeMemory
1338246niehFoehn Phenomena (JOI17_foehn_phenomena)C++17
100 / 100
179 ms11468 KiB
#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define FOD(i, a, b) for(int i = (a); i >= (b); i--)
#define file(name) if(fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#define el cout << '\n'
#define maxn int(2e5 + 5)

using namespace std;

typedef long long ll;

int n, q, S, T;

ll a[maxn];

namespace subtask1 {
    bool check() {
        return n <= 2000;
    }

    void solve() {
        while(q--) {
            ll res = 0;
            int l, r, x;
            cin >> l >> r >> x;
            FOR(i, l, r) a[i] += x;
            FOR(i, 1, n) {
                if(a[i] > a[i - 1]) res -= 1LL * S * abs(a[i] - a[i - 1]);
                else res += 1LL * T * abs(a[i] - a[i - 1]);
            }
            cout << res, el;
        }
    }
}

namespace subtask3 {

    ll d[maxn];

    ll t[maxn << 2];

    void update(int pos, ll val, int id = 1, int l = 1, int r = n) {
        if(pos < l || r < pos) return;
        if(l == r) {
            t[id] = val;
            return;
        }
        int mid = (l + r) >> 1;
        update(pos, val, id << 1, l, mid);
        update(pos, val, id << 1 | 1, mid + 1, r);
        t[id] = t[id << 1] + t[id << 1 | 1];
    }

    void updatePoint(int i) {
        if(d[i] > 0) update(i, -1LL * S * abs(d[i]));
        else update(i, 1LL * T * abs(d[i]));
    }

    void solve() {
        FOR(i, 1, n) {
            d[i] = a[i] - a[i - 1];
            updatePoint(i);
        }
        while(q--) {
            int l, r, x;
            cin >> l >> r >> x;
            d[l] += x;
            d[r + 1] -= x;
            updatePoint(l);
            if(r + 1 <= n) updatePoint(r + 1);
            cout << t[1], el;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> q >> S >> T;
    FOR(i, 0, n) cin >> a[i];
    if(subtask1::check()) return subtask1::solve(), 0;
    return subtask3::solve(), 0;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...