제출 #1258789

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1258789		hanguyen	Foehn Phenomena (JOI17_foehn_phenomena)	C++20	100 / 100	310 ms	13072 KiB

foehn_phenomena

#include <bits/stdc++.h>
using namespace std;

int n,q,A[200005];
long long s,t,st[800005],laz[800005],res=0;

void build(int id, int l, int r){
    if (l==r){
        st[id]=A[l];
        return;
    }
    int m=(l+r)>>1;
    build(id<<1,l,m);
    build(id<<1|1,m+1,r);
    st[id]=st[id<<1]+st[id<<1|1];
}

void fix(int id, int l, int r){
    if (!laz[id]) return;
    st[id]+=laz[id]*(r-l+1);
    if (l!=r){
        laz[id<<1]+=laz[id];
        laz[id<<1|1]+=laz[id];
    }
    laz[id]=0;
}

void update(int id, int l, int r, int u, int v, int val){
    fix(id,l,r);
    if (v<l || r<u) return;
    if (u<=l && r<=v){
        laz[id]+=val;
        fix(id,l,r);
        return;
    }
    int m=(l+r)>>1;
    update(id<<1,l,m,u,v,val);
    update(id<<1|1,m+1,r,u,v,val);
    st[id]=st[id<<1]+st[id<<1|1];
}

long long get(int id, int l, int r, int i){
    fix(id,l,r);
    if (i<l || r<i) return 0;
    if (l==r) return st[id];
    int m=(l+r)>>1;
    if (i<=m) return get(id<<1,l,m,i);
    else return get(id<<1|1,m+1,r,i);
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(nullptr);

    cin >> n >> q >> s >> t;
    for (int i=0; i<=n; i++){
        cin >> A[i];
        if (i==0) continue;
        if (A[i]>A[i-1]) res-=(A[i]-A[i-1])*s;
        else res+=(A[i-1]-A[i])*t;
    }
    build(1,0,n);

    while (q--){
        int l,r,x; cin >> l >> r >> x;
        long long val;

        if (l>0){
            long long beff=get(1,0,n,l-1),leff=get(1,0,n,l);
            if (leff>beff) res += (leff-beff)*s;
            else res -= (beff-leff)*t;
        }
        if (r<n){
            long long reff=get(1,0,n,r),aeff=get(1,0,n,r+1);
            if (aeff>=reff) res += (aeff-reff)*s;
            else res -= (reff-aeff)*t;
        }

        update(1,0,n,l,r,x);

        if (l>0){
            long long bef=get(1,0,n,l-1),lef=get(1,0,n,l);
            if (lef>=bef) res -= (lef-bef)*s;
            else res += (bef-lef)*t;
        }
        if (r<n){
            long long ref=get(1,0,n,r),aef=get(1,0,n,r+1);
            if (aef>=ref) res -= (aef-ref)*s;
            else res += (ref-aef)*t;
        }

        cout << res << "\n";
    }
}

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