Submission #1005684

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005684		MarwenElarbi	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	506 ms	16468 KiB

foehn_phenomena

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ii pair<int,int>
template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int nax=2e5+5;
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
long long segtree[nax*4];
long long tab[nax];
void build(int pos,int l,int r){
    if(l==r){
        segtree[pos]=tab[l];
        return;
    }
    int mid=(r+l)/2;
    build(pos*2+1,l,mid);
    build(pos*2+2,mid+1,r);
    return;
}
void update(int pos,int l,int r,int left,int right,int value){
    if(l>r||l>right||r<left) return;
    if(l>=left&&r<=right){
        segtree[pos]+=value;
        return;
    }
    int mid=(r+l)/2;
    update(pos*2+1,l,mid,left,right,value);
    update(pos*2+2,mid+1,r,left,right,value);
    return;
}
long long query(int pos,int l,int r,int idx){
    if(l==r) return segtree[pos];
    int mid=(r+l)/2;
    if(idx<=mid) return segtree[pos]+query(pos*2+1,l,mid,idx);
    else return segtree[pos]+query(pos*2+2,mid+1,r,idx);
}
int main()
{
    optimise;   
    int n,q,s,t;
    cin>>n>>q>>s>>t;
    for (int i = 0; i <= n; ++i)
    {
        cin>>tab[i];
    }
    build(0,0,n);
    long long sum=0;
    for (int i = 1; i <= n; ++i)
    {
        if(tab[i-1]<tab[i]) sum+=1ll*s*(tab[i-1]-tab[i]);
        else sum+=1ll*t*(tab[i-1]-tab[i]);
    }
    while(q--){
        int l,r,x;
        cin>>l>>r>>x;
        long long left=query(0,0,n,l);
        long long lefty=query(0,0,n,l-1);
        long long right=query(0,0,n,r);
        long long righty;
        if(r<n) righty=query(0,0,n,r+1);
        update(0,0,n,l,r,x);
        if(lefty<left) sum-=1ll*s*(lefty-left);
        else sum-=1ll*t*(lefty-left);
        long long cnt=query(0,0,n,l);
        if(lefty<cnt) sum+=1ll*s*(lefty-cnt);
        else sum+=1ll*t*(lefty-cnt);
        if(r<n){
            cnt=query(0,0,n,r);
            if(right<righty) sum-=1ll*s*(right-righty);
            else sum-=1ll*t*(right-righty);
            if(cnt<righty) sum+=1ll*s*(cnt-righty);
            else sum+=1ll*t*(cnt-righty);

        }
        cout <<sum<<endl;
        /*if(tab[l-1]<tab[l]) sum+=1ll*s*(tab[l-1]-tab[l]);
        else sum+=1ll*t*(tab[l-1]-tab[l]);
        cnt=tab[l]+x;
        if(tab[l-1]<cnt) sum-=1ll*s*(tab[l-1]-cnt);
        else sum-=1ll*t*(tab[l-1]-cnt);
        if(r<n){
            cnt=tab[r]+x;
            if(tab[r]<tab[r+1]) sum+=1ll*s*(tab[r]-tab[r+1]);
            else sum+=1ll*t*(tab[r]-tab[r+1]);
            if(cnt<tab[r+1]) sum-=1ll*s*(cnt-tab[r+1]);
            else sum-=1ll*t*(cnt-tab[r+1]);
        }*/
    }
}

Compilation message (stderr)

foehn_phenomena.cpp: In function 'int main()':
foehn_phenomena.cpp:77:47: warning: 'righty' may be used uninitialized in this function [-Wmaybe-uninitialized]
   77 |             if(right<righty) sum-=1ll*s*(right-righty);
      |                                         ~~~~~~^~~~~~~~

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