제출 #1287267

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1287267		Born_To_Laugh	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	82 ms	7264 KiB

foehn_phenomena

// Born_To_Laugh - Hughie Do
#include <bits/stdc++.h>
#define alle(AC) AC.begin(), AC.end()
#define fi first
#define se second
using namespace std;
typedef long long ll;
[[maybe_unused]] const ll MOD = 998244353, INF = 1e9 + 7;
#define int ll
const int maxn = 2e5 + 10;
struct Fenwick_Tree
{
    vector<int> bit;
    int n;
    Fenwick_Tree(){
        n = maxn - 1;
        bit.assign(n + 1, 0);
    }
    void PointUpd(int pos, int val){
        for(; pos<=n; pos += pos & -pos)bit[pos] += val;
    }
    int get(int pos){
        int ans = 0;
        for(; pos>0; pos -= pos & -pos)ans += bit[pos];
        return ans;
    }
};

Fenwick_Tree ft;
int n, q, s, t;
int ori[maxn];
ll ans = 0;
void solve(){
    cin >> n >> q >> s >> t;
    for(int i=1; i<=n + 1; ++i){
        cin >> ori[i];
        ft.PointUpd(i, ori[i] - ori[i - 1]);
        if(i == 1)continue;
        if(ori[i - 1] < ori[i]) ans += (ori[i - 1] - ori[i]) * s;
        else ans += (ori[i - 1] - ori[i]) * t;
    }
    while(q--){
        int l, r, x;cin >> l >> r >> x;
        l++;r++;
        if(l != 1){
            int val = ft.get(l);
            int nxt = val + x;
            int pre = ft.get(l - 1);
            int cc1, cc2;
            if(pre < val)cc1 = (pre - val) * s;
            else cc1 = (pre - val) * t;
            if(pre < nxt)cc2 = (pre - nxt) * s;
            else cc2 = (pre - nxt) * t;
            ans += (cc2 - cc1);
            ft.PointUpd(l, x);
        }
        if(r != n + 1){
            int val = ft.get(r + 1);
            int nxt = val - x;
            int pre = ft.get(r);
            int cc1, cc2;
            if(pre < val)cc1 = (pre - val) * s;
            else cc1 = (pre - val) * t;
            if(pre < nxt)cc2 = (pre - nxt) * s;
            else cc2 = (pre - nxt) * t;
            ans += (cc2 - cc1);
            ft.PointUpd(r + 1, -x);
        }
        cout << ans << '\n';
    }
}
signed main(){
    // freopen("inp.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
}

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