Submission #949708

#	Time	Username	Problem	Language	Result	Execution time	Memory
949708		placik	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	196 ms	15800 KiB

foehn_phenomena

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define int long long
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(ll i=(ll)a;i<=(ll)b;++i)
#define all(a) a.begin(),a.end()
#define sz(x) (int)(x).size()
const int mxN = 2e5+7, base = 1<<18;
int a[mxN], tree[base<<1];

void init(int n){
    rep(i,0,n) tree[i+base] = a[i];
}

void add(int l,int r,int x){
    l += base-1;
    r += base+1;
    while(r-l > 1){
        if(!(l&1)) tree[l+1] += x;
        if(r&1) tree[r-1] += x;
        l /= 2; r /= 2;
    }
}

int que(int v){
    v += base;
    int res = tree[v];
    while(v){
        v /= 2;
        res += tree[v];
    }

    return res;
}

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,q,s,t; cin >> n >> q >> s >> t;
    rep(i,0,n) cin >> a[i];

    init(n);

    int rosnie = 0, spada = 0;
    rep(i,1,n) if(a[i] > a[i-1]) rosnie += a[i]-a[i-1];
    rep(i,1,n) if(a[i] < a[i-1]) spada += a[i-1]-a[i];

    while(q--){
        int l,r,x; cin >> l >> r >> x;
        if(que(l) > que(l-1)) rosnie -= que(l)-que(l-1);
        if(r < n) if(que(r+1) > que(r)) rosnie -= que(r+1)-que(r);
        if(que(l) < que(l-1)) spada += que(l)-que(l-1);
        if(r < n) if(que(r+1) < que(r)) spada += que(r+1)-que(r);
        add(l,r,x);
        if(que(l) > que(l-1)) rosnie += que(l)-que(l-1);
        if(r < n) if(que(r+1) > que(r)) rosnie += que(r+1)-que(r);
        if(que(l) < que(l-1)) spada -= que(l)-que(l-1);
        if(r < n) if(que(r+1) < que(r)) spada -= que(r+1)-que(r);

        cout << -rosnie*s + spada*t << "\n";
    }
}

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