Submission #1263656

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263656		nguyenhuythach	Foehn Phenomena (JOI17_foehn_phenomena)	C++20	100 / 100	76 ms	8772 KiB

foehn_phenomena

#include<bits/stdc++.h>
#include<algorithm>
#include<random>
#include<chrono>
#include<cstdlib>
#include<ctime>
#include<numeric>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<iomanip>
#define int long long
#define ll long long
#define L LLONG_MAX
#define fi first
#define se second
#define pii pair<int,int>
#define sz(a) ((int)a.size())
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define REP(i,k,j) for(int i=k;i>=j;i--)
#define FORD(i,a) for(auto i:a)
#define rngdcl mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(l,r) ((l)+(rng()%(r-l+1)))
using namespace std;
const int nmax=2e5+1;
int n,q,s,t;
int a[nmax],tree[nmax],dif[nmax];

void update(int x,int val)
{
    while(x<=n+1)
    {
        tree[x]+=val;
        x+=(x&-x);
    }
}

int get(int x)
{
    int ans=0;
    while(x>0)
    {
        ans+=tree[x];
        x-=(x&-x);
    }
    return ans;
}

void input()
{
    cin >> n >> q >> s >> t;
    FOR(i,0,n) cin >> a[i];
}

void solve()
{
    FOR(i,1,n) dif[i]=a[i]-a[i-1];
    FOR(i,1,n) update(i,dif[i]);
    int ans=0;
    FOR(i,0,n-1)
    {
        if(a[i]<a[i+1]) ans-=s*(a[i+1]-a[i]);
        else ans+=t*(a[i]-a[i+1]);
    }
    while(q--)
    {
        int l,r,x; cin >> l >> r >> x;
        int cs=r;
        int prel=get(l),prer=get(r);
        update(r+1,-x);
        update(l,x);
        int savel=get(l-1),saver=get(r+1);
        l=get(l);
        r=get(r);
        if(savel<prel) ans+=s*(prel-savel);
        else ans-=t*(savel-prel);
        if(savel<l) ans-=s*(l-savel);
        else ans+=t*(savel-l);
        if(cs!=n)
        {
            if(r<saver) ans-=s*(saver-r);
            else ans+=t*(r-saver);
            if(prer<saver) ans+=s*(saver-prer);
            else ans-=t*(prer-saver);
        }
        cout << ans << '\n';
    }
}

signed main()
{
    //freopen(".inp", "r", stdin);
    //freopen(".out", "w", stdout);
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    input();
    solve();
}

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