Submission #735295

#	Time	Username	Problem	Language	Result	Execution time	Memory
735295		tigar	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	361 ms	14472 KiB

foehn_phenomena

#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);
    }
}

ll 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]);
        if(d1>=0)windspid+=s*d1;
        else windspid+=t*d1;
        if(d2>=0)windspid+=s*d2;
        else windspid+=t*d2;

        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(nj1>=0)windspid-=s*nj1;
        else windspid-=t*nj1;
        if(nj2>=0)windspid-=s*nj2;
        else windspid-=t*nj2;

        cout<<windspid<<"\n";
    }
    return 0;
}

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