Submission #287058

#	Time	Username	Problem	Language	Result	Execution time	Memory
287058		MasterTaster	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	0 / 100	1039 ms	25300 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"

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

void relax(int node, int l, int 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(int node, int l, int 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(int node, int l, int r)
{
    if (l==r)
    {
        seg[node]=arr[l];
        return;
    }
    int mid=l+(r-l)/2;
    build(2*node, l, mid);
    build(2*node+1, mid+1, r);
}
void buildT(int node, int l, int r)
{
    if (l==r)
    {
        //cout<<l<<" "<<temp[l]<<endl;
        segT[node]=temp[l];
        return;
    }
    int mid=l+(r-l)/2;
    buildT(2*node, l, mid);
    buildT(2*node+1, mid+1, r);
}

void update(int node, int l, int r, int levo, int 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)
    {
        seg[node]+=val;
        if (l!=r)
        {
            lazy[2*node]+=val;
            lazy[2*node+1]+=val;
        }
        return;
    }

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

void updateT(int node, int l, int r, int levo, int 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)
    {
        segT[node]+=val;
        if (l!=r)
        {
            lazyT[2*node]+=val;
            lazyT[2*node+1]+=val;
        }
        return;
    }

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

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

    int 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(int node, int l, int r, int levo, int desno)
{
    relaxT(node, l, r);
    if (levo>r || desno<l) return -1000000000010;
    if (levo<=l && desno>=r) { /*cout<<l<<" alo "<<segT[node]<<endl;*/  return segT[node]; }

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

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);
    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 stariPrvi, stariDrugi;
            stariPrvi=query(1, 0, n, l-1, l-1);
            stariDrugi=query(1, 0, n, l, l);
            ll noviPrvi=stariPrvi, noviDrugi=stariDrugi+x;

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

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

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

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

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

        //cout<<"eeeej"<<endl;
        cout<<queryT(1, 0, n, n, n)<<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: 0 / 30
• Subtask 2: 0 / 10
• Subtask 3: 0 / 60