Submission #1165023

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165023		filipsumic	Foehn Phenomena (JOI17_foehn_phenomena)	C++20	100 / 100	363 ms	13956 KiB

foehn_phenomena

#include <bits/stdc++.h>
#define pb push_back
#define ll long long int
#define pi pair<int, int>
#define all(x) x.begin(), x.end()

using namespace std;


const int nmax=2*1e5+5;

ll seg[4*nmax];
ll lazy[4*nmax];


void push(int cvor, int l, int r)
{
    if(lazy[cvor]==0) return;
    seg[cvor]+=(r-l+1)*lazy[cvor];
    if(l<r)
    {
        lazy[2*cvor]+=lazy[cvor];
        lazy[2*cvor+1]+=lazy[cvor];
    }
    lazy[cvor]=0;
}

void Build(int cvor, int l, int r, vector<ll>& niz)
{
    if(l==r)
    {
        seg[cvor]=niz[l];
        return;
    }
    int mid=l+(r-l)/2;
    Build(cvor*2, l, mid, niz);
    Build(cvor*2+1, mid+1, r, niz);
    seg[cvor]=seg[cvor*2]+seg[cvor*2+1];
}
void Update(int cvor, int l, int r, ll lt, ll rt, ll x)
{
    push(cvor, l, r);
    if(l>rt || r<lt) return;
    if(l>=lt && r<=rt)
    {
        lazy[cvor]+=x;
        push(cvor, l, r);
        return;
    }
    int mid=l+(r-l)/2;
    Update(cvor*2, l, mid, lt, rt, x);
    Update(cvor*2+1, mid+1, r, lt, rt, x);
    seg[cvor]=seg[cvor*2]+seg[cvor*2+1];
}

ll Query(int cvor, int l, int r, ll lt, ll rt)
{
    push(cvor, l, r);
    if(l>rt || r<lt) return 0;
    if(l>=lt && r<=rt) return seg[cvor];
    int mid=l+(r-l)/2;
    return Query(2*cvor, l, mid, lt, rt)+Query(2*cvor+1, mid+1, r, lt, rt);
}




int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    ll n, q, s, t;
    cin>>n>>q>>s>>t;
    vector<ll> visine(n+1);
    for(int i=0; i<n+1; i++)
    {
        cin>>visine[i];
    }
    Build(1, 0, n, visine);
    ll temp=0;
    for(int i=1; i<n+1; i++)
    {
        if(visine[i-1]<visine[i])
        {
            temp=temp-s*(visine[i]-visine[i-1]);
        }
        else
        {
            temp=temp+t*(visine[i-1]-visine[i]);
        }
    }
    for(int i=0; i<q; i++)
    {
        ll l, r, x;
        cin>>l>>r>>x;
        ll lpret=Query(1, 0, n, l-1, l-1);
        ll lsad=Query(1, 0, n, l, l);
        ll rsad=Query(1, 0, n, r, r);
        ll rsled;
        if(r<n) rsled=Query(1, 0, n, r+1, r+1);
        Update(1, 0, n, l, r, x);
        ll lsadnov=Query(1, 0, n, l, l);
        ll rsadnov=Query(1, 0, n, r, r);
        //promena na tacci l
        if(lpret<lsad && lpret<lsadnov)
        {
            temp=temp+s*(lsad-lsadnov);
        }
        else if(lpret<lsad && lpret>=lsadnov)
        {
            temp=temp+s*(lsad-lpret)+t*(lpret-lsadnov);
        }
        else if(lpret>=lsad && lpret>=lsadnov)
        {
            temp=temp+t*(lsad-lsadnov);
        }
        else
        {
            temp=temp-t*(lpret-lsad)-s*(lsadnov-lpret);
        }
        //promena na tacci r
        if(r<n)
        {
            if(rsad<rsled && rsadnov<rsled)
            {
                temp=temp+s*(rsled-rsad)-s*(rsled-rsadnov);
            }
            else if(rsad<rsled && rsadnov>=rsled)
            {
                temp=temp+s*(rsled-rsad)+t*(rsadnov-rsled);
            }
            else if(rsad>=rsled && rsadnov>=rsled)
            {
                temp=temp+t*(rsadnov-rsad);
            }
            else
            {
                temp=temp-t*(rsad-rsled)-s*(rsled-rsadnov);
            }
        }
        cout<<temp<<"\n";
    }
}

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