Submission #998339

#	Time	Username	Problem	Language	Result	Execution time	Memory
998339		dimashhh	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	353 ms	32848 KiB

foehn_phenomena

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int  N = 3e5 + 30, MOD = 1e9 + 7;
#define int ll 
int n,a[N],q,s,f;
ll all = 0,add[N * 4];
struct node{
    ll sum = 0,l = 0,r = 0;
    bool empty = false;
}t[N * 4];
node merge(node a,node b){
    if(a.empty) return b;
    if(b.empty) return a;
    a.sum += b.sum;
    if(a.r < b.l){
        a.sum -= (b.l - a.r) * s;
    }else{
        a.sum += (a.r - b.l) * f;
    }
    a.r = b.r;
    return a;
}
void build(int v = 1,int tl = 1,int tr = n){
    if(tl == tr){
        t[v].l = t[v].r = a[tl];
        t[v].sum = 0;
    }else{
        int tm = (tl + tr) >> 1;
        build(v + v,tl,tm);
        build(v + v + 1,tm + 1,tr);
        t[v] = merge(t[v + v],t[v + v + 1]);
    }
}
void inc(int v,int val){
    t[v].l += val;
    t[v].r += val;
    add[v] += val;
}
void push(int v){
    if(add[v]){
        inc(v + v,add[v]);
        inc(v + v + 1,add[v]);
        add[v] = 0;
    }
}
void upd(int l,int r,int val,int v = 1,int tl = 1,int tr = n){
    if(l > r || tl > r || l > tr) return;
    if(tl >= l && tr <= r){
        inc(v,val);
    }else{
        push(v);
        int tm = (tl + tr) >> 1;
        upd(l,r,val,v+v,tl,tm);
        upd(l,r,val,v+v+1,tm+1,tr);
        t[v] = merge(t[v + v],t[v + v + 1]);
    }
}
void test(){
    cin >> n >> q >> s >> f;
    n++;
    for(int i = 1;i <= n;i++){
        cin >> a[i];
    }
    build();
    // cout << t[1].sum << '\n';   
    while(q--){
        int l,r,x;
        cin >> l >> r >> x;
        l++;r++;
        // cout << l << ' ' << r << ' ' << x << '\n';
        upd(l,r,x);
        cout << t[1].sum << '\n';
    }
}
signed main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    int t = 1;
    // cin >> t;
    while(t--){
        test();
    }
}

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