Submission #1287747

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287747		kiteyu	Foehn Phenomena (JOI17_foehn_phenomena)	C++20	0 / 100	1097 ms	1616 KiB

foehn_phenomena

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5;

int n,q,s,t;
int a[N+5];
int S[N+5],B=2,S1[N+5],lz[N+5];

ll ans = 0;
bool op(int x,int y){
    if(x < y) swap(x,y);
    return (x >= 0 && y < 0);
}

int get(int x){
    return (a[x] >= 0 ? a[x] + lz[x / B] : a[x] - lz[x / B]);
}

void cal(int x,int ty){
    int cur = get(x);
    if(x < n){
        int nxt = get(x + 1);
//        cout << cur << '.' << nxt << '\n';
        if(cur < nxt) ans -= ty * (nxt - cur) * s;
        else ans += ty * (cur - nxt) * t;
    }

    if(x > 0){
        int pre = get(x - 1);
//        cout << pre << '.' << cur << '\n';
        if(pre < cur) ans -= ty * (cur - pre) * s;
        else ans += ty * (pre - cur)* t;
    }
}

void upd(int x,int val){
    cal(x,-1);
//    cout << ans << "pha1\n";
    a[x] = a[x] + val;
//    a[x] = (a[x] >= 0 ? a[x] + val : a[x] - val);
    cal(x,1);
//    cout << ans << "pha2\n";
}

void cal1(int x,int y,int ty){
    int cur = get(x);
    int cur1 =get(y);
//    cout << cur << ',' << cur1 << "\n";
    if(cur < cur1) ans -= ty * (cur1 - cur) * s;
    else ans += ty * (cur - cur1) * t;
}

void upd1(int x, int y,int val,int ty){
    if(y > n) return;
    cal1(x,y,-1);

    if(ty == 0) a[y] =a[y] + val;
    else a[x] = a[x] + val;
    cal1(x,y,1);
    if(ty == 0) a[y] =a[y] - val;
    else a[x] = a[x] - val;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> q >> s >> t;
    for(int i = 0 ; i <= n ; ++i) cin >> a[i];
    for(int i = 0 ; i < n ; ++i){
        if(a[i] < a[i + 1]){
            ans -= (a[i + 1] - a[i]) * s;
        }
        else{
            ans += (a[i] - a[i + 1]) * t;
        }
//        if(i / B == (i + 1) / B && op(a[i],a[i + 1])){
//            if(a[i] >= 0) S[i / B]++;
//            else S1[i / B]++;
//        }
    }

//    cout << ans << "!\n";

    while(q--){
        int l,r,x;
        cin >> l >> r >> x;
        for(int i = l ; i <= r ; ++i){
            if(i % B == 0 && i + B - 1 <= r){

                upd1(i-1,i,x,0);
                upd1(i + B - 1,i+B,x,1);

                lz[i/B] += x;
//                cout << S[i/B] << '?' << S1[i/B] << '.' << lz[i/B] << '.' << i + B - 1 << ',' << a[i + B - 1] << '.' << get(i + B - 1) << '\n';

                i += B - 1;
            }
            else{
                upd(i,x);
            }
        }
        cout << ans << '\n';
    }

    return 0;
}

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