Submission #287504

#	Time	Username	Problem	Language	Result	Execution time	Memory
287504		MasterTaster	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	672 ms	21496 KiB

foehn_phenomena

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define pii pair<int, int>
#define xx first
#define yy second
#define endl "\n"
#define MAXN 1000000000000000000

ll n, q, s, t, arr[200010], seg[800040], temp[200010], lazy[800040], segT[800040], lazyT[800040];

void relax(ll node, ll l, ll r)
{
    ll val=lazy[node];
    seg[node]+=lazy[node];
    lazy[node]=0;
    if (l!=r)
    {
        lazy[2*node]+=val;
        lazy[2*node+1]+=val;
    }
    return;
}
void relaxT(ll node, ll l, ll r)
{
    ll val=lazyT[node];
    segT[node]+=lazyT[node];
    lazyT[node]=0;
    if (l!=r)
    {
        lazyT[2*node]+=val;
        lazyT[2*node+1]+=val;
    }
    return;
}

void build(ll node, ll l, ll r)
{
    if (l==r)
    {
        seg[node]=arr[l];
        return;
    }
    ll mid=l+(r-l)/2;
    build(2*node, l, mid);
    build(2*node+1, mid+1, r);
    return;
}
void buildT(ll node, ll l, ll r)
{
    if (l==r)
    {
        //cout<<l<<" "<<temp[l]<<endl;
        segT[node]=temp[l];
        return;
    }
    ll mid=l+(r-l)/2;
    buildT(2*node, l, mid);
    buildT(2*node+1, mid+1, r);
    return;
}

void update(ll node, ll l, ll r, ll levo, ll desno, ll val) ///l, r-gde sam u segmentnom; levo, desno-query
{
    relax(node, l, r);
    if (levo>r || desno<l) return;
    if (levo<=l && desno>=r)
    {
        lazy[node]+=val;
        return;
    }

    ll mid=l+(r-l)/2;
    update(2*node, l, mid, levo, desno, val);
    update(2*node+1, mid+1, r, levo, desno, val);
    relax(2*node, l, mid);
    relax(2*node+1, mid+1, r);
    seg[node]=max(seg[2*node], seg[2*node+1]);
}

void updateT(ll node, ll l, ll r, ll levo, ll desno, ll val) ///l, r-gde sam u segmentnom; levo, desno-query
{
    relaxT(node, l, r);
    if (levo>r || desno<l) return;
    if (levo<=l && desno>=r)
    {
        lazyT[node]+=val;
        return;
    }

    ll mid=l+(r-l)/2;
    updateT(2*node, l, mid, levo, desno, val);
    updateT(2*node+1, mid+1, r, levo, desno, val);
    relaxT(2*node, l, mid);
    relaxT(2*node+1, mid+1, r);
    segT[node]=max(segT[2*node], segT[2*node+1]);
}

ll query(ll node, ll l, ll r, ll levo, ll desno)
{
    relax(node, l, r);
    if (levo>r || desno<l) return (ll)-MAXN;
    if (levo<=l && desno>=r) return seg[node];

    ll mid=l+(r-l)/2;
    return max(query(2*node, l, mid, levo, desno),
               query(2*node+1, mid+1, r, levo, desno));
}

ll queryT(ll node, ll l, ll r, ll levo, ll desno)
{
    relaxT(node, l, r);
    if (levo>r || desno<l) return (ll)-MAXN;
    if (levo<=l && desno>=r) { /*cout<<l<<" alo "<<segT[node]<<endl;*/  return segT[node]; }

    ll mid=l+(r-l)/2;
    return max(queryT(2*node, l, mid, levo, desno),
               queryT(2*node+1, mid+1, r, levo, desno));
}

ll out;

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>>arr[i];

    temp[0]=0;
    for (int i=1; i<=n; i++)
    {
        if (arr[i]>arr[i-1]) temp[i]=temp[i-1]-s*(arr[i]-arr[i-1]);
        else temp[i]=temp[i-1]+t*(arr[i-1]-arr[i]);
        ///cout<<temp[i]<<endl;
    }

    build(1, 0, n);
    out=temp[n];
    //buildT(1, 0, n);
    //cout<<temp[n]<<" e "<<queryT(1, 0, n, n, n)<<endl;

    ///cout<<"ee"<<endl;
    while (q--)
    {
        ll l, r, x;
        cin>>l>>r>>x;

        ///A[i]>=A[i-1], T[i-1]-S*DELTA
        ///A[i]<A[i-1], T[i-1]+T*DELTA

        ll delta=0;
        if (l>0)
        {
            ll prvi, stariDrugi;
            prvi=query(1, 0, n, l-1, l-1);
            stariDrugi=query(1, 0, n, l, l);
            ll noviDrugi=stariDrugi+x;

            ///cout<<stariPrvi<<" e "<<stariDrugi<<" e "<<noviDrugi<<endl;

            if (x>=0)
            {
                if (stariDrugi<prvi)
                {
                    delta-=t*(min(noviDrugi, prvi)-stariDrugi); ///OK
                }
                if (noviDrugi>=prvi)
                {
                    delta-=s*(noviDrugi-max(stariDrugi, prvi));
                }
            }
            else
            {
                if (stariDrugi>=prvi)
                {
                    delta+=s*(stariDrugi-max(prvi, noviDrugi)); ///OK
                }
                if (noviDrugi<prvi)
                {
                    delta+=t*(min(stariDrugi, prvi)-noviDrugi); ///OK
                }
            }
        }
        ///if (delta!=0) updateT(1, 0, n, l, n, delta);
        out+=delta;
        ///cout<<delta<<endl;
        ///cout<<"eej"<<endl;
        delta=0;
        if (r<n)
        {
            ll stariPrvi, drugi;
            stariPrvi=query(1, 0, n, r, r);
            drugi=query(1, 0, n, r+1, r+1);
            ll noviPrvi=stariPrvi+x;

            ///cout<<stariPrvi<<" "<<stariDrugi<<" "<<noviPrvi<<endl;

            if (x<0)
            {
                if (drugi<stariPrvi)
                {
                    delta-=t*(stariPrvi-max(noviPrvi, drugi)); ///OK
                }
                if (drugi>=noviPrvi)
                {
                    delta-=s*(min(drugi, stariPrvi)-noviPrvi); ///OK
                }
            }
            else
            {
                ///cout<<"ovde"<<endl;
                if (drugi>=stariPrvi)
                {
                    ///cout<<"jee"<<endl;
                    delta+=s*(min(drugi, noviPrvi)-stariPrvi); ///OK
                }
                if (noviPrvi>drugi)
                {
                    ///cout<<"dvaa"<<endl;
                    delta+=t*(noviPrvi-max(stariPrvi, drugi)); ///OK
                }
            }
        }
        ///if (delta!=0) updateT(1, 0, n, r+1, n, delta);
        ///cout<<delta<<endl;
        out+=delta;

        //cout<<"eeej"<<endl;
        update(1, 0, n, l, r, x);

        //cout<<"eeeej"<<endl;
        cout<<out<<endl;
    }
}

/*for (int i=l; i<=r; i++) arr[i]+=x;

        temp=0;
        for (int i=1; i<=n; i++)
        {
            if (arr[i]>arr[i-1])
            {
                temp=temp-s*(arr[i]-arr[i-1]);
            }
            else
                temp=temp+t*(arr[i-1]-arr[i]);
        }
        cout<<temp<<endl;*/

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