Submission #1208778

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208778		andrejikus	Foehn Phenomena (JOI17_foehn_phenomena)	C++20	100 / 100	85 ms	7240 KiB

foehn_phenomena

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) { cerr << to_string(h); if(sizeof...(t)) cerr << ", "; DBG(t...); }
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)

const int N = 2e5 + 3;
ll a[N];

struct fenwick_tree {
    vector<ll> bit;
    void init(int n) {
        bit.assign(n + 1, 0ll);
    }

    ll sum(int i) {
        ll s = 0;
        while (i > 0) {
            s += bit[i];
            i -= (i & (-i));
        }
        return s;
    }
    void add(int i, ll val, int n) {
        while (i > 0 && i <= n) {
            bit[i] += val;
            i += (i & (-i));
        }
    }
    ll get(int l, int r) {
        return sum(r) - (l > 0 ? sum(l-1) : 0);
    }
}; fenwick_tree fenwick;

void solve() {
    ll n, q, s, t; cin >> n >> q >> s >> t;
    fenwick.init(n+1);
    for (int i = 0; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) {
        fenwick.add(i, a[i], n+1);
        fenwick.add(i+1, -a[i], n+1);
    }

    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i-1] < a[i])
            ans -= (a[i]-a[i-1])*s;
        else
            ans += (a[i-1]-a[i])*t;
    }

    while (q--) {
        ll l, r, x; cin >> l >> r >> x;

        ll al = fenwick.get(0, l), alm1 = fenwick.get(0, l-1);
        ll arp1 = fenwick.get(0, r+1), ar = fenwick.get(0, r);

        if (al > alm1)
            ans += (al-alm1)*s;
        else ans -= (alm1-al)*t;

        if (r < n) {
            if (arp1 > ar)
                ans += (arp1-ar)*s;
            else ans -= (ar-arp1)*t;
        }

        fenwick.add(r+1, -x, n+1);
        fenwick.add(l, x, n+1);

        al = fenwick.get(0, l), alm1 = fenwick.get(0, l-1);
        arp1 = fenwick.get(0, r+1), ar = fenwick.get(0, r);

        if (al > alm1)
            ans -= (al-alm1)*s;
        else ans += (alm1-al)*t;

        if (r < n) {
            if (arp1 > ar)
                ans -= (arp1-ar)*s;
            else ans += (ar-arp1)*t;
        }

        cout << ans << "\n";
    }
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(0);
	int t=1; //cin >> t;
	while (t--) {
        solve();
	}
}

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