Submission #1275510

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275510		quanduongxuan12	Foehn Phenomena (JOI17_foehn_phenomena)	C++20	100 / 100	352 ms	13928 KiB

foehn_phenomena

#include <bits/stdc++.h>
using namespace std;
#define name "foehn"
#define MAXN 200005
#define pb push_back
#define pf push_front
#define ll long long
#define ii pair<int, int>
#define fs first
#define sc second
#define ill pair<int, ll>
#define lli pair<ll, int>
#define llll pair<ll, ll>
#define all(v) v.begin(),v.end()
#define uni(v) v.erase(unique(all(v)),v.end())
#define bit(n,i) (((n)>>(i))&1)
#define FOR(i,a,b) for (int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for (int i=(a),_b=(b); i>=_b; i--)
#define MASK(i) (1LL<<(i))
const int INF=1e9;
const int MOD=1e9+7;
void add(int &u, int v){
    u+=v;
    if (u>=MOD) u-=MOD;
}
void sub(int &u, int v){
    u-=v;
    if (u<0) u+=MOD;
}
void minimize(int &u, int v){
    u=min(u,v);
}
void maximize(int &u, int v){
    u=max(u,v);
}
long long Rand(long long l, long long r){
    ll tmp=0;
    FOR(i,1,4) tmp=((tmp<<15)^(((1<<15)-1)&rand()));
    return l+tmp%(r-l+1);
}
int n,q,s,t;
ll a[MAXN];
ll st[4*MAXN],lazy[4*MAXN];
void build(int id, int l, int r){
    if (l==r){
        st[id]=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(id<<1,l,mid);
    build(id<<1|1,mid+1,r);
    st[id]=st[id<<1]+st[id<<1|1];
}
void down(int id, int l, int r){
    if (lazy[id]==0||l==r) return;
    int mid=(l+r)/2;
    st[id<<1]+=1LL*(mid-l+1)*lazy[id];
    st[id<<1|1]+=1LL*(r-mid)*lazy[id];
    lazy[id<<1]+=lazy[id];
    lazy[id<<1|1]+=lazy[id];
    lazy[id]=0;
}
void update(int id, int l, int r, int u, int v, int val){
    if (l>v||r<u) return;
    if (l>=u&&r<=v){
        st[id]+=1LL*(r-l+1)*val;
        lazy[id]+=val;
        down(id,l,r);
        return;
    }
    down(id,l,r);
    int mid=(l+r)/2;
    update(id<<1,l,mid,u,v,val);
    update(id<<1|1,mid+1,r,u,v,val);
    st[id]=st[id<<1]+st[id<<1|1];
}
ll get(int id, int l, int r, int u, int v){
    if (l>v||r<u) return 0;
    if (l>=u&&r<=v) return st[id];
    down(id,l,r);
    int mid=(l+r)/2;
    return get(id<<1,l,mid,u,v)+get(id<<1|1,mid+1,r,u,v);
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin>>n>>q>>s>>t;
    FOR(i,0,n) cin>>a[i];
    ll res=0;
    FOR(i,0,n-1){
        if (a[i]<a[i+1]){
            res-=1LL*s*(a[i+1]-a[i]);
        }
        else res+=1LL*t*(a[i]-a[i+1]);
    }
    build(1,1,n);
    while (q--){
        int l,r,val;
        cin>>l>>r>>val;
        ll u=get(1,1,n,l,l);
        ll x=get(1,1,n,r,r);
        update(1,1,n,l,r,val);
        ll v=get(1,1,n,l,l);
        ll y=get(1,1,n,r,r);

        ll tmp=(l==1?0LL:get(1,1,n,l-1,l-1));
        a[l-1]=tmp;
        a[l]=u;
        if (a[l-1]<a[l]){
            res+=1LL*s*(a[l]-a[l-1]);
        }
        else{
            res-=1LL*t*(a[l-1]-a[l]);
        }
        a[l]=v;
        if (a[l-1]<a[l]){
            res-=1LL*s*(a[l]-a[l-1]);
        }
        else{
            res+=1LL*t*(a[l-1]-a[l]);
        }
        if (r<n){
            ll tmp=get(1,1,n,r+1,r+1);
            a[r+1]=tmp;
            a[r]=x;
            if (a[r]<a[r+1]){
                res+=1LL*s*(a[r+1]-a[r]);
            }
            else{
                res-=1LL*t*(a[r]-a[r+1]);
            }
            a[r]=y;
            if (a[r]<a[r+1]){
                res-=1LL*s*(a[r+1]-a[r]);
            }
            else{
                res+=1LL*t*(a[r]-a[r+1]);
            }
        }
        cout<<res<<"\n";
    }
    return 0;
}

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