제출 #1258753

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1258753		khanhtt	Foehn Phenomena (JOI17_foehn_phenomena)	C++20	100 / 100	380 ms	13240 KiB

foehn_phenomena

#include <iostream>
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;
    return get(id<<1,l,m,i)+get(id<<1|1,m+1,r,i);
}
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 beff=get(1,0,n,l-1),leff=get(1,0,n,l);
        long long val;
        if (leff>beff){
            val=(leff-beff)*s;
            res+=val;
        }
        else{
            val=(beff-leff)*t;
            res-=val;
        }
        if (r<n){
            long long aeff=get(1,0,n,r+1),reff=get(1,0,n,r);
            if (aeff>=reff){
                val=(aeff-reff)*s;
                res+=val;
            }
            else{
                val=(reff-aeff)*t;
                res-=val;
            }
        }
        update(1,0,n,l,r,x);
        long long bef=get(1,0,n,l-1),lef=get(1,0,n,l);
        if (lef>=bef){
            val=(lef-bef)*s;
            res-=val;
        }
        else{
            val=(bef-lef)*t;
            res+=val;
        }
        if (r<n){
            long long aef=get(1,0,n,r+1),ref=get(1,0,n,r);
            if (aef>=ref){
                val=(aef-ref)*s;
                res-=val;
            }
            else{
                val=(ref-aef)*t;
                res+=val;
            }
        }
        cout << res << "\n";
    }
}

컴파일 시 표준 에러 (stderr) 메시지

foehn_phenomena.cpp:44:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   44 | main(){
      | ^~~~

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