Submission #1285736

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285736		khoavn2008	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	30 / 100	1095 ms	2276 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,int 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;
    vector<ll> a(n + 1, 0);
    FOR(i,0,n)cin>>a[i];
    while(q--){
        ll l,r,x;cin>>l>>r>>x;
        FOR(i,l,r)a[i] += x;
        ll ans = 0;
        FOR(i,1,n){
            if(a[i - 1] < a[i])ans += (a[i - 1] - a[i]) * s;
            else ans += (a[i - 1] - a[i]) * t;
        }
        cout<<ans<<endl;
    }
//    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: 0 / 10
• Subtask 3: 0 / 60