Submission #1347278

#TimeUsernameProblemLanguageResultExecution timeMemory
1347278kantaponzFoehn Phenomena (JOI17_foehn_phenomena)C++20
100 / 100
62 ms7232 KiB
#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int nx = 2e5 + 5;

int n, q;
ll s, t, a[nx], height[nx], mor, les;

void update(int idx, ll val) {
    for (int i = idx; i < nx; i += (i & -i)) {
        height[i] += val;
    }
}

ll query(int idx) {
    ll sum = 0;
    for (int i = idx; i >= 1; i -= (i & -i)) {
        sum += height[i];
    }
    return sum;
}



int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> n >> q >> s >> t;
    for (int i = 0; i <= n; i++) {
        cin >> a[i];
        if (i > 0) {
            if (a[i] - a[i - 1] > 0) {
                mor += a[i] - a[i - 1];
            } else {
                les += a[i - 1] - a[i];
            }
            //cout << a[i] - a[i - 1] << " ";
            update(i, a[i]-a[i-1]);
        }
    }
    //cout << "\n";
    //cout << mor << " " << les << " " << les*t - mor*s << endl;


    while (q--) {
        int l, r;
        ll x;
        cin >> l >> r >> x;
        
        ll pl = query(l - 1), cl = query(l), nr = query(r + 1), cr = query(r);
        
        if (pl > cl) les -= (pl - cl);
        else mor -= (cl - pl);

        if (cl + x - pl > 0) mor += cl + x - pl;
        else les += pl - cl - x;

        if (r + 1 <= n) {
            if (nr < cr) les -= (cr - nr);
            else mor -= (nr - cr);
        
            if (nr - cr - x > 0) mor += nr - cr - x;
            else les += x + cr - nr;
        }

        update(l, x);
        update(r + 1, -x);

        /*for (int i = 0; i <= n; i++) {
            cout << query(i) << " ";
        } cout << endl;*/

        //cout << mor << " " << les << endl;
        //cout << pl << " " << cl << " " << cr << " " << nr << endl;

        cout << les*t - mor*s << "\n";

        //cout << "---------\n";
    }
}

/*
3 5 1 2
0
4
1
8
1 2 2
1 1 -2
2 3 5
1 2 -1
1 3 5

-5
-7
-13
-13
-18

*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...