Submission #735274

#TimeUsernameProblemLanguageResultExecution timeMemory
735274tigarFoehn Phenomena (JOI17_foehn_phenomena)C++14
30 / 100
350 ms13984 KiB
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll n, q, s, t;
ll a[200020], l[200020], r[200020], x[200020];
ll segtree[800080];

void build(ll v, ll tl, ll tr)
{
    if(tl==tr){segtree[v]=a[tl];}
    else
    {
        ll tm=(tl+tr)/2;
        build(v*2, tl, tm);
        build(v*2+1, tm+1, tr);
        segtree[v]=0;
    }
}

void update(ll v, ll tl, ll tr, ll l, ll r, ll add)
{
    if(l>r)return;
    if(l==tl && r==tr){segtree[v]+=add;}
    else
    {
        ll tm=(tl + tr)/2;
        update(v*2, tl, tm, l, min(r, tm), add);
        update(v*2+1, tm+1, tr, max(l, tm+1), r, add);
    }
}

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>n>>q>>s>>t;
    for(int i=0; i<=n; i++)cin>>a[i];
    for(int i=0; i<q; i++)cin>>l[i]>>r[i]>>x[i];

    ll windspid=0;
    for(int i=0; i<n; i++)
    {
        if(a[i]<a[i+1])windspid-=s*(a[i+1]-a[i]);
        else windspid+=t*(a[i]-a[i+1]);
    }
    build(1, 0, n);
    for(int i=0; i<q; i++)
    {
        ll d1=get(1, 0, n, l[i])-get(1, 0, n, l[i]-1), d2=get(1, 0, n, min(r[i]+1, n))-get(1, 0, n, r[i]);
        update(1, 0, n, l[i], r[i], x[i]);
        ll nj1=get(1, 0, n, l[i])-get(1, 0 , n, l[i]-1), nj2=get(1, 0, n, min(r[i]+1, n))-get(1, 0, n, r[i]);
        if(d1>0)windspid+=s*d1;
        else windspid+=t*d1;
        if(nj1>0)windspid-=s*nj1;
        else windspid-=t*nj1;

        if(d2>0)windspid+=s*d2;
        else windspid+=t*d2;
        if(nj2>0)windspid-=s*nj2;
        else windspid-=t*nj2;
        cout<<windspid<<"\n";
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...