Submission #1285776

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285776		khoavn2008	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	140 ms	7160 KiB

foehn_phenomena

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld double
#define FOR(i,l,r) for(int i = (l), _r = (r); i <= _r; i++)
#define FORNG(i,r,l) for(int i = (r), _l = (l); i >= _l; i--)
#define REP(i,r) for(int i = 0, _r = (r); i < _r; i++)
#define endl '\n'
#define fi first
#define se second
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define size(v) ((ll)(v).size())
#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)

const ll MOD = 1e9 + 7, N = 3e5 + 10, INF = 1e18, LOG = 32;
struct Fenwick{
    int n;
    vector<ll> fen;
    Fenwick(ll n = 0):n(n){
        fen.assign(n + 1, 0);
    }
    void update(int p,ll v){
        for(;p<=n;p+=p&-p)fen[p]+=v;
    }
    ll get(int p){
        ll res = 0;
        for(;p;p-=p&-p)res+=fen[p];
        return res;
    }
}S,H;
int n,q;
ll s,t,a[N];
void upd(ll pos,ll c){
    if(pos > n)return;
    if(H.get(pos - 1) < H.get(pos)){
        S.update(pos, -(H.get(pos) - H.get(pos - 1)) * s * c);
    }else{
        S.update(pos, (H.get(pos - 1) - H.get(pos)) * t * c);
    }
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>q>>s>>t;
    S = Fenwick(n);
    H = Fenwick(n);
    FOR(i,0,n){
        ll a;cin>>a;
        if(i){
            H.update(i,a);
            H.update(i + 1,-a);
            upd(i, 1);
        }
    }
    while(q--){
        ll l,r,x;cin>>l>>r>>x;
        upd(l, -1);
        upd(r + 1, -1);
        H.update(l, x);
        H.update(r + 1, -x);
        upd(l, 1);
        upd(r + 1, 1);
        cout<<S.get(n)<<endl;
    }
}

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