제출 #538430

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
538430		__Variatto	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	215 ms	13176 KiB

foehn_phenomena

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define ll long long
const int MAX=2e5+10, SS=1<<18;
ll n, q, S, T, d[2*SS+10];
void Insert(int a, int b, int w){
    a+=SS-1, b+=SS+1;
    while(a+1<b){
        if(a%2==0) d[a+1]+=w;
        if(b%2==1) d[b-1]+=w;
        a/=2, b/=2;
    }
}
ll Query(int a){
    a+=SS;
    ll wyn=0;
    while(a){
        wyn+=d[a];
        a/=2;
    }
    return wyn;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin>>n>>q>>S>>T;
    ll last=0, akt=0;
    for(int i=1; i<=n+1; i++){
        int curr;
        cin>>curr;
        Insert(i-1, i-1, curr);
        if(i>1){
            if(curr>last) akt-=(curr-last)*S;
            else akt+=(last-curr)*T;
        }
        last=curr;
    }
    for(int i=1; i<=q; i++){
        ll l, r, x;
        cin>>l>>r>>x;
        ll popLewy=Query(l-1),  lewy=Query(l), prawy=Query(r), nastPrawy=Query(r+1);
        if(lewy>popLewy) akt+=(lewy-popLewy)*S;
        else akt-=(popLewy-lewy)*T;
        if(r<n){
            if(nastPrawy>prawy) akt+=(nastPrawy-prawy)*S;
            else akt-=(prawy-nastPrawy)*T;
        }
        Insert(l, r, x);
        popLewy=Query(l-1),  lewy=Query(l), prawy=Query(r), nastPrawy=Query(r+1);
        if(lewy>popLewy) akt-=(lewy-popLewy)*S;
        else akt+=(popLewy-lewy)*T;
        if(r<n){
            if(nastPrawy>prawy) akt-=(nastPrawy-prawy)*S;
            else akt+=(prawy-nastPrawy)*T;
        }
        cout<<akt<<"\n";
    }
}

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