Submission #289650

#	Time	Username	Problem	Language	Result	Execution time	Memory
289650		rocks03	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	629 ms	13364 KiB

foehn_phenomena

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pld pair<long double, int>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define ff first
#define ss second
#define SZ(x) ((int)(x).size())
#define ld long double
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAXN = 2e5+100;
int N, Q;
ll S, T, a[MAXN];

void read(){
    cin >> N >> Q >> S >> T;
    for(int i = 0; i <= N; i++){
        cin >> a[i];
    }
}

ll b[MAXN];
void add(int i, int k){
    for(; i < MAXN; i += (i & -i))
        b[i] += k;
}
ll get(int i){
    ll s = 0;
    for(; i > 0; i -= (i & -i))
        s += b[i];
    return s;
}

pll compare(int i){
    pll diff = {0, 0};
    ll ob1 = get(i), ob2 = get(i-1);
    if(i - 1 >= 0 && ob1 > ob2){
        diff.ss += ob1 - ob2;
    } else if(i - 1 >= 0 && ob2 > ob1){
        diff.ff += ob2 - ob1;
    }
    return diff;
}

ll ans;
pll cur;
void preprocess(){
    for(int i = 1; i <= N; i++){
        add(i, a[i]);
        add(i+1, -a[i]);
    }
    for(int i = 1; i <= N; i++){
        pll diff = compare(i);
        cur.ff += diff.ff, cur.ss += diff.ss;
    }
    ans = cur.ff * T - cur.ss * S;
}

void update(int l, int r, int x){
    pll diff;
    diff = compare(l);
    cur.ff -= diff.ff, cur.ss -= diff.ss;
    if(r+1 <= N){
        diff = compare(r+1);
        cur.ff -= diff.ff, cur.ss -= diff.ss;
    }
    add(l, x);
    add(r+1, -x);
    diff = compare(l);
    cur.ff += diff.ff, cur.ss += diff.ss;
    if(r+1 <= N){
        diff = compare(r+1);
        cur.ff += diff.ff, cur.ss += diff.ss;
    }
    ans = cur.ff * T - cur.ss * S;
}

void solve(){
    read();
    preprocess();
    while(Q--){
        int l, r, x;
        cin >> l >> r >> x;
        update(l, r, x);
        cout << ans << "\n";
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    solve();
    return 0;
}

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