제출 #1309927

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1309927		okahak71	Foehn Phenomena (JOI17_foehn_phenomena)	C++20	100 / 100	337 ms	18304 KiB

foehn_phenomena

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pll array<ll, 2>
#define lll array<ll, 3>
#define endl '\n'
#define all(X) X.begin(), X.end()
using namespace std;

struct SGT{
    vector<ll>st, lz;
    SGT(ll n){st.assign(4 * n + 5, 0), lz.assign(4 * n + 5, 0);}
    void build(ll l, ll r, ll v, vector<ll> &a){
        if(l == r){
            st[v] = a[l];
            return ;
        }
        ll mid = (l + r) / 2;
        build(l , mid , v << 1, a);
        build(mid + 1, r , v << 1 | 1, a);
        st[v] = st[v << 1] + st[v << 1 | 1];
    }
    void lazy(ll l, ll r, ll v, vector<ll> &a){
        if(!lz[v]) return ;
        st[v] += (r - l + 1) * lz[v];
        if(l != r){
            lz[v << 1] += lz[v];
            lz[v << 1 | 1] += lz[v];
        }
        else
            a[l] += lz[v];
        lz[v] = 0;
    }
    ll find(ll l, ll r, ll id, ll v, vector<ll> &a){
        lazy(l, r, v, a);
        if(l == r) return st[v];
        ll mid = (l + r) / 2;
        if(id <= mid) return find(l, mid, id, v << 1, a);
        return find(mid + 1, r, id, v << 1 | 1, a);
    }
    void upd(ll l, ll r, ll ql, ll qr, ll vl, ll v, vector<ll> &a){
        lazy(l, r, v, a);
        if(r < ql or qr < l) return ;
        if(ql <= l and r <= qr){
            lz[v] += vl;
            lazy(l, r, v, a);
            return ;
        }
        ll mid = (l + r) / 2;
        upd(l, mid, ql, qr, vl, v << 1, a);
        upd(mid + 1, r, ql, qr, vl, v << 1 | 1, a);
        st[v] = st[v << 1] + st[v << 1 | 1];
    }
};

void _(){
    ll n, q, s, t, ans = 0;
    cin >> n >> q >> s >> t;
    vector<ll>a(n + 1); SGT sg(n + 1);
    for(ll &i : a) cin >> i; sg.build(1, n, 1, a);
    for(ll i = 0; i < n; i++){
        ans += (a[i] - a[i + 1]) * (a[i] < a[i + 1] ? s : t);
    }
    while(q--){
        ll l, r, x; cin >> l >> r >> x;
        if(l > 1) sg.find(1, n, l - 1, 1, a);
        if(r < n) sg.find(1, n, r + 1, 1, a);
        sg.find(1, n, l, 1, a); sg.find(1, n, r, 1, a);
        ans -= (a[l - 1] - a[l]) * (a[l - 1] < a[l] ? s : t);
        if(r < n) ans -= (a[r] - a[r + 1]) * (a[r] < a[r + 1] ? s : t);
        sg.upd(1, n, l, r, x, 1, a);
        if(l > 1) sg.find(1, n, l - 1, 1, a);
        if(r < n) sg.find(1, n, r + 1, 1, a);
        sg.find(1, n, l, 1, a); sg.find(1, n, r, 1, a);
        ans += (a[l - 1] - a[l]) * (a[l - 1] < a[l] ? s : t);
        if(r < n) ans += (a[r] - a[r + 1]) * (a[r] < a[r + 1] ? s : t);
        //for(ll i = 1; i <= n; i++) cout << a[i] << ' '; cout << endl;
        cout << ans << endl;
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0); _();
}

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