Submission #463297

#	Time	Username	Problem	Language	Result	Execution time	Memory
463297		JasperL	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	945 ms	14580 KiB

foehn_phenomena

// to speed up code, use fenwick!

#include <iostream>
#include <vector>
using namespace std;
#define maxn 200005
typedef long long ll;

int n,q; ll s,t;

ll gap(ll a, ll b) {
    if (a < b) return (a-b) * s;
    else return (a-b) * t;
}

ll a[maxn];
ll d[maxn]; // difference array, d[1] + d[2] + ... + d[i] == a[i]
ll z[maxn]; // fenwick for temperature

void inc(int i, ll x) {
    for (; i <= n; i += i&(-i)) d[i] += x;
}
ll get(int i) {
    ll ret = 0;
    for (; i; i -= i&(-i)) ret += d[i];
    return ret;
}
void aug(int i, ll x) {
    for (; i <= n; i += i&(-i)) z[i] += x;
}
ll temp(int i) {
    ll ret = 0;
    for (; i; i -= i&(-i)) ret += z[i];
    return ret;
}

int main() {
    cin >> n >> q >> s >> t;
    for (int i = 0; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) inc(i,a[i]-a[i-1]);
    for (int i = 0; i < n; i++) aug(i+1,gap(get(i),get(i+1)));
    for (int i = 0; i < q; i++) {
        int l, r; ll x; cin >> l >> r >> x;
        ll L = get(l-1), R = get(l);
        ll u = gap(L,R), v = gap(L,R+x);
        aug(l,v-u);
        if (r != n) {
            L = get(r), R = get(r+1);
            u = gap(L,R), v = gap(L+x,R);
            aug(r+1,v-u);
        }
        inc(l,x); 
        if (r != n) inc(r+1,-x);
        cout << temp(n) << endl;
    }
}   

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