제출 #1310049

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1310049		tnt	Foehn Phenomena (JOI17_foehn_phenomena)	C++20	0 / 100	289 ms	12524 KiB

foehn_phenomena

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast,fast-math,O3")

#define pb push_back                    
#define ll long long  
#define f first
#define s second
#define int long long
//#define sz(v) int(v.size())
#define all(v) v.begin(),v.end()

int mod =  1e9 + 7;
const int N = 2e5 + 2,k = 317 + 1;
const int inf = 2e9;
int d[N * 4],tr[N * 4],a[N];
int n,q,s,t,ans;
int func(int x,int y){
    if(x < y) return (x - y) * s;
    else return (x - y) * t;
}
void build(int u,int l,int r){
    if(l == r){
        tr[u] = a[l];
        return;
    }
    int mid = (l + r) / 2;
    build(u * 2,l,mid),build(u * 2 + 1,mid + 1,r);
}
void push(int u,int l,int r){   
    int mid = (l + r) / 2;
    tr[u] += d[u];
    if(l != r)d[u * 2] += d[u],d[u * 2 + 1] += d[u];
    d[u] = 0;
}
void upd(int u,int l,int r,int lx,int rx,int x){
    push(u,l,r);
    if(l >= lx && r <= rx){
        d[u] += x;
        push(u,l,r);
        return;
    }
    else if(l > rx || r < lx) return;
    int mid = (l + r) / 2;
    upd(u * 2,l,mid,lx,rx,x);
    upd(u * 2 + 1,mid + 1,r,lx,rx,x);
}
int get(int u,int l,int r,int lx,int rx){
    push(u,l,r);
    if(l >= lx && r <= rx) return tr[u];
    else if(l > rx || r < lx) return 0;
    int mid = (l + r) / 2;
    return get(u * 2,l,mid,lx,rx) + get(u * 2 + 1,mid + 1,r,lx,rx);
}
void solve(){
    cin >> n >> q >> s >> t;
    for(int i = 0; i <= n; i++){
        cin >> a[i];
    }
    for(int i = 1; i <= n; i++){
        ans += func(a[i - 1],a[i]);
    }
    build(1,0,n);
    while(q--){
        int l,r,x;
        cin >> l >> r >> x;
        upd(1,0,n,l,r,x);
        if(l != 0)ans -= func(a[l - 1],a[l]);
        if(r != n) ans -= func(a[r],a[r + 1]);
        a[r] = get(1,0,n,r,r);
        a[l] = get(1,0,n,l,l);
        if(l != 0){
            a[l - 1] = get(1,0,n,l - 1,l - 1);
            ans += func(a[l - 1],a[l]);
        }
        if(r != n){
            a[r + 1] = get(1,0,n,r + 1,r + 1);
            ans += func(a[r],a[r + 1]);
        }
        cout << ans << '\n';
    }
    
}
signed main(){
    //freopen("time.in", "r", stdin);
    //freopen("time.out", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t = 1;
    while(t--){
        solve();
    }
}                          	

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