Submission #463258

#	Time	Username	Problem	Language	Result	Execution time	Memory
463258		JasperL	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	30 / 100	1064 ms	15248 KiB

foehn_phenomena

#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;

#define maxn 200005

int n,q; ll s,t;
ll st[4*maxn], la[4*maxn];
ll bt[maxn];

void inc(int i, ll val) {
    for (; i <= n; i += (i&(-i))) bt[i] += val;
}
ll temp(int i) {
    ll ret = 0;
    for (; i; i -= (i&(-i))) ret += bt[i];
    return ret;
}

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

void push(int i, int l, int r) {
    if (la[i] != 0) {
        st[i] += la[i] * (ll)(r-l+1);
        if (l != r) la[2*i] += la[i], la[2*i+1] += la[i];
        la[i] = 0;
    }
}
void pull(int i, int l, int r) {
    push(2*i,l,(l+r)/2); push(2*i+1,(l+r)/2+1,r);
    st[i] = st[2*i] + st[2*i+1];
}
void aug(int i, int l, int r, int L, int R, ll val) {
    push(i,l,r);
    if (L <= l && r <= R) {
        la[i] += val; return;
    }
    if (r < L || R < l) return;
    aug(2*i,l,(l+r)/2,L,R,val), aug(2*i+1,(l+r)/2+1,r,L,R,val);
    pull(i,l,r);
}
void aug(int idx, ll val) {
    aug(1,0,n,idx,idx,val);
}
void aug(int l, int r, ll val) {
    aug(1,0,n,l,r,val);
}
ll get(int i, int l, int r, int idx) {
    push(i,l,r);
    if (l == r) return st[i];
    if (idx <= (l+r)/2) return get(2*i,l,(l+r)/2,idx);
    else return get(2*i+1,(l+r)/2+1,r,idx);
}
ll get(int idx) {
    return get(1,0,n,idx);
}

int main() {
    cin >> n >> q >> s >> t;
    for (int i = 0; i <= n; i++) {
        ll a; cin >> a;
        aug(i,a);
    }
    for (int i = 0; i < n; i++) {
        ll a = get(i), b = get(i+1);
        inc(i+1,gap(a,b));
    }
    /*
    for (int i = 1; i <= n; i++) {
        cout << temp(i) - temp(i-1) << " ";
    }
    cout << endl;
    */
    for (int i = 0; i < q; i++) {
        int l,r; ll x; cin >> l >> r >> x;
        ll a = get(l-1), b = get(l);
        // we go from b --> b + x
        ll u = gap(a,b), v = gap(a,b+x);
        inc(l,v-u);
        if (r != n) {
            a = get(r), b = get(r+1);
            u = gap(a,b), v = gap(a+x,b);
            inc(r+1,v-u);
        }
        aug(l,r,x);
        cout << temp(n) << endl;
    }
}

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