Submission #396545

#	Time	Username	Problem	Language	Result	Execution time	Memory
396545		teehandsome	Foehn Phenomena (JOI17_foehn_phenomena)	C++11	100 / 100	299 ms	9796 KiB

foehn_phenomena

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define INF 1e9+7
#define all(x) x.begin(),x.end()
using namespace std;
using namespace __gnu_pbds;
using ll=long long;
using pii=pair<int,int>;
using ppi=pair<int,pii>;
using oset=tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>;

template<typename T>
void _print(vector<T> x) {cerr<<"{"; for(auto e:x) cerr<<e<<","; cerr<<"}";}
void _print(pii x) {cerr<<"{"<<x.first<<","<<x.second<<"}";}
template<typename T>
void _print(T x) {cerr<<x;}

void dbg() {cerr<<endl;}
template<typename Head,typename... Tail>
void dbg(Head H,Tail... T) {
    _print(H);
    if(sizeof...(T)) cerr<<",";
    else cerr<<"\"]";
    dbg(T...);
}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:[\"",dbg(__VA_ARGS__)

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int mxn=2e5+10;
ll n,m,S,T;
vector<ll> a;
ll t[3*mxn];
bool flag[3*mxn];

void build(int v,int tl,int tr) {
    if(tl==tr) t[v]=a[tl];
    else {
        int mid=(tl+tr)/2;
        build(2*v,tl,mid);
        build(2*v+1,mid+1,tr);
    }
}

void add(int v,int tl,int tr,int l,int r,int val) {
    if(tl>tr or tl>r or tr<l) return;
    if(tl>=l and tr<=r) t[v]+=val;
    else {
        int mid=(tl+tr)/2;
        add(2*v,tl,mid,l,r,val);
        add(2*v+1,mid+1,tr,l,r,val);
    }
}

ll get(int v,int tl,int tr,int idx) {
    if(tl==tr) return t[v];
    int mid=(tl+tr)/2;
    if(idx<=mid) return t[v]+get(2*v,tl,mid,idx);
    else return t[v]+get(2*v+1,mid+1,tr,idx);
}

void print() {
    for(int i=0;i<n;i++) {
        cout<<get(1,0,n-1,i)<<" ";
    }
    cout<<endl;
}

ll f(ll u,ll v) {
    if(u<v) return -1LL*S*(v-u);
    return 1LL*T*(u-v);
}

int main () {
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n>>m>>S>>T; n++;
    a.resize(n);
    for(int i=0;i<n;i++) cin>>a[i];
    build(1,0,n-1);
    ll ans=0;
    for(int i=1;i<n;i++) {
        ans+=f(a[i-1],a[i]);
    }
//    debug(ans);
    for(int i=0;i<m;i++) {
        ll l,r,x; cin>>l>>r>>x;
        if(l-1>=0) {
            ll a1=get(1,0,n-1,l-1);
            ll a2=get(1,0,n-1,l);
//            debug(a1,a2,f(a1,a2));
            ans-=f(a1,a2);
            ans+=f(a1,a2+x);
        }
        if(r+1<n) {
            ll a1=get(1,0,n-1,r);
            ll a2=get(1,0,n-1,r+1);
            ans-=f(a1,a2);
            ans+=f(a1+x,a2);
        }
        add(1,0,n-1,l,r,x);
        cout<<ans<<endl;
    }

}

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