Submission #288254

#	Time	Username	Problem	Language	Result	Execution time	Memory
288254		FEDIKUS	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	484 ms	24284 KiB

foehn_phenomena

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define xx first
#define yy second
#define srt(a) sort(a.begin(),a.end());
#define srtg(a,ll) sort(a.begin(),a.end(),greater<ll>())
#define lb(a,x) lower_bound(a.begin(),a.end(),x)
#define up(a,x) upper_bound(a.begin(),a.end(),x)
#define fnd(a,x) find(a.begin(),a.end(),x)
#define vstart auto startt=chrono::system_clock::now()
#define vend auto endd=chrono::system_clock::now()
#define vvreme chrono::duration<double> vremee=endd-startt
#define ios ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair<ll,ll> pii;
typedef pair<ll,ll> pll;
typedef string str;

ll n,q,s,t;
vector<ll> visine;
vector<ll> segt;
vector<ll> lazy;

void build(ll ind,ll l,ll r){
    if(l==r) segt[ind]=visine[l];
    if(l==r) return;
    ll mid=l+(r-l)/2;
    build(2*ind,l,mid);
    build(2*ind+1,mid+1,r);
}

void update(ll ind,ll l,ll r,ll tl,ll tr,ll x){
    if(tl==l && tr==r){
        lazy[ind]+=x;
        return;
    }
    if(l==r) return;
    ll mid=l+(r-l)/2;
    if(tl<=mid){
        update(2*ind,l,mid,tl,min(mid,tr),x);
    }
    if(tr>mid){
        update(2*ind+1,mid+1,r,max(tl,mid+1),tr,x);
    }
}

ll query(ll ind,ll l,ll r,ll a){
    if(l!=r && lazy[ind]!=0){
        lazy[2*ind]+=lazy[ind];
        lazy[2*ind+1]+=lazy[ind];
        lazy[ind]=0;
    }
    if(l==r && l==a){
        segt[ind]+=lazy[ind];
        lazy[ind]=0;
        return segt[ind];
    }
    ll mid=l+(r-l)/2;
    if(a<=mid){
        return query(2*ind,l,mid,a);
    }else{
        return query(2*ind+1,mid+1,r,a);
    }
}

ll raz(ll a){
    ll prvi=query(1,0,n,a);
    ll drugi=(a+1==visine.size() ? query(1,0,n,a):query(1,0,n,a+1));
    if(prvi>drugi){
        return (prvi-drugi)*t;
    }else return -(drugi-prvi)*s;
}

int main()
{
    ios;
    cin>>n>>q>>s>>t;
    visine.resize(n+1);
    for(ll i=0;i<=n;i++) cin>>visine[i];
    vector<ll> temp(n+1);
    segt.resize(4*n+4,0);
    lazy.resize(4*n+4,0);
    build(1,0,n);
    temp[0]=0;
    for(ll i=1;i<=n;i++){
        if(visine[i]>visine[i-1]){
            temp[i]=temp[i-1]-(visine[i]-visine[i-1])*s;
        }else{
            temp[i]=temp[i-1]+(visine[i-1]-visine[i])*t;
        }
    }
    ll res=temp[n];
    while(q--){
        ll l,r,x;
        cin>>l>>r>>x;
        res-=raz(l-1);
        res-=raz(r);
        update(1,0,n,l,r,x);
        res+=raz(l-1);
        res+=raz(r);
        cout<<res<<"\n";
    }
    return 0;
}

Compilation message (stderr)

foehn_phenomena.cpp: In function 'll raz(ll)':
foehn_phenomena.cpp:75:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     ll drugi=(a+1==visine.size() ? query(1,0,n,a):query(1,0,n,a+1));
      |               ~~~^~~~~~~~~~~~~~~

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