제출 #1139622

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1139622		altern23	Foehn Phenomena (JOI17_foehn_phenomena)	C++20	100 / 100	90 ms	7240 KiB

foehn_phenomena

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

#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
 
#define ll long long
#define pii pair<ll,ll>
#define fi first
#define sec second
#define ld long double

ostream& operator << (ostream& os, pii x){
    os << "[";
    os << " " << x.fi << " " << x.sec;
    os << " ]";
 
    return os;
}

ostream& operator << (ostream& os, pair<pii, ll> x){
    os << "[";
    os << " " << x.fi << " " << x.sec;
    os << " ]";
 
    return os;
}

ostream& operator << (ostream& os, pair<ll, pii> x){
    os << "[";
    os << " " << x.fi << " " << x.sec;
    os << " ]";
 
    return os;
}

template <typename T>
ostream& operator << (ostream& os, vector<T>tmp){
    os << "[";
    for(auto x : tmp) os << " " << x;
    os << " ]";
 
    return os;
}

template <typename T>
ostream& operator << (ostream& os, set<T>tmp){
    os << "[";
    for(auto x : tmp) os << " " << x;
    os << " ]";
 
    return os;
}
 
template <typename T>
ostream& operator << (ostream& os, multiset<T>tmp){
    os << "[";
    for(auto x : tmp) os << " " << x;
    os << " ]";
 
    return os;
}

const ll MOD = 998244353;
const ll N = 5e3;
const ll INF = 2e18;

// modulo operations
void add(ll &a, ll b) { a = (a + b) % MOD; }
void sub(ll &a, ll b) { a -= b; while(a < 0) a += MOD; a %= MOD; }
void mul(ll &a, ll b) { a = (a * b) % MOD; }

ll expo(ll a, ll b) {
    ll ans = 1;
    while(b > 0){
        if(b & 1) mul(ans, a);
        mul(a, a);
        b /= 2;
    }

    return ans;
}

struct fenwick{
    ll n;
    vector<ll> bit;
    fenwick(ll size){
        n = size;
        bit.resize(n + 5);
    }
    void upd(ll idx, ll val){
        for(int i = idx; i <= n; i += i & -i) bit[i] += val;
    }
    ll get(ll idx){
        ll ans = 0;
        for(int i = idx; i >= 1; i -= i & -i) ans += bit[i];
        return ans;
    }
    ll query(ll l, ll r){
        return get(r) - get(l - 1);
    }
};

int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int tc = 1;
    // cin >> tc;
    for(;tc--;){
        ll n, q, s, t; cin >> n >> q >> s >> t;
        
        fenwick bit(n + 5);
        vector<ll> a(n + 5);

        for(int i = 0; i <= n; i++){
            cin >> a[i];
            if(i != 0){
                bit.upd(i, a[i]);
                bit.upd(i + 1, -a[i]);
            }
        }

        ll ans = 0;
        for(int i = 1; i <= n; i++){
            if(a[i] <= a[i - 1]) ans += (a[i - 1] - a[i]) * t;
            else ans -= (a[i] - a[i - 1]) * s;
        }

        auto del = [&](ll idx){
            if(idx > n || idx < 1) return;
            ll A = bit.query(1, idx), B = (idx - 1 == 0 ? 0 : bit.query(1, idx - 1));
            if(A <= B) ans -= (B - A) * t;
            else ans += (A - B) * s;
        };

        auto ins = [&](ll idx){
            if(idx > n || idx < 1) return;
            ll A = bit.query(1, idx), B = (idx - 1 == 0 ? 0 : bit.query(1, idx - 1));
            if(A <= B) ans += (B - A) * t;
            else ans -= (A - B) * s;
        };

        for(int i = 1; i <= q; i++){
            ll l, r, x; cin >> l >> r >> x;
            del(l), del(r + 1);
            bit.upd(l, x);
            bit.upd(r + 1, -x);
            ins(l), ins(r + 1);
                
            cout << ans << "\n";
        }
    }   
}

/*

*/

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