Submission #931118

#	Time	Username	Problem	Language	Result	Execution time	Memory
931118		De3b0o	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	409 ms	22508 KiB

foehn_phenomena

#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define in insert
#define er erase
#define pb push_back
#define ppb pop_back()
#define ph push
#define pp pop()
#define d3 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define cans cout << ans << "\n";
#define yes cout << "YES" << "\n";
#define no cout << "NO" << "\n";
#define pll pair<ll,ll>
#define lin cout << "\n";
#define sqr 340
#define mod 1000000007
#define mid (l+r)/2

using namespace std;

ll seg[800009];
ll lazy[800009];
ll a[200009];

void sb(ll n , ll l , ll r)
{
    if(l==r)
    {
        seg[n]=a[l];
        return;
    }
    sb(2*n,l,mid);
    sb(2*n+1,mid+1,r);
    seg[n]=seg[2*n]+seg[2*n+1];
}

ll sg(ll n , ll l , ll r , ll i)
{
    if(l>i||r<i)
        return 0;
    seg[n]+=lazy[n]*(r-l+1);
    if(l!=r)
    {
        lazy[2*n]+=lazy[n];
        lazy[2*n+1]+=lazy[n];
    }
    lazy[n]=0;
    if(l==r)
        return seg[n];
    return sg(2*n,l,mid,i)+sg(2*n+1,mid+1,r,i);
}

void su(ll n , ll l , ll r , ll l1 , ll r1 , ll x)
{
    if(l>r1||r<l1)
        return;
    if(l>=l1&&r<=r1)
    {
        lazy[n]+=x;
        return;
    }
    su(2*n,l,mid,l1,r1,x);
    su(2*n+1,mid+1,r,l1,r1,x);
}

int main()
{
    d3
    ll n , q , s , t;
    cin >> n >> q >> s >> t;
    for(int i = 0 ; n>=i ; i++)
        cin >> a[i];
    sb(1,0,n);
    ll ans = 0;
    for(int i = 0 ; n>i ; i++)
    {
        ll ans1 = a[i]-a[i+1];
        if(a[i]<a[i+1])
            ans1*=s;
        else
            ans1*=t;
        ans+=ans1;
    }
    while(q--)
    {
        ll l , r , x;
        cin >> l >> r >> x;
        if(l)
        {
            ll x1 = sg(1,0,n,l-1);
            ll x2 = sg(1,0,n,l);
            ll ans1 = x1-x2;
            if(x1<x2)
                ans1*=s;
            else
                ans1*=t;
            ans-=ans1;
        }
        if(r<n)
        {
            ll x1 = sg(1,0,n,r);
            ll x2 = sg(1,0,n,r+1);
            ll ans1 = x1-x2;
            if(x1<x2)
                ans1*=s;
            else
                ans1*=t;
            ans-=ans1;
        }
        su(1,0,n,l,r,x);
        if(l)
        {
            ll x1 = sg(1,0,n,l-1);
            ll x2 = sg(1,0,n,l);
            ll ans1 = x1-x2;
            if(x1<x2)
                ans1*=s;
            else
                ans1*=t;
            ans+=ans1;
        }
        if(r<n)
        {
            ll x1 = sg(1,0,n,r);
            ll x2 = sg(1,0,n,r+1);
            ll ans1 = x1-x2;
            if(x1<x2)
                ans1*=s;
            else
                ans1*=t;
            ans+=ans1;
        }
        cans
    }
}

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