Submission #359274

#	Time	Username	Problem	Language	Result	Execution time	Memory
359274		shahriarkhan	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	618 ms	14060 KiB

foehn_phenomena

#include<bits/stdc++.h>
using namespace std ;

#define ll long long

struct lazy_tree
{
    vector<ll> lazy ;

    lazy_tree(ll a[] , int low , int n)
    {
        lazy = vector<ll> (4*n + 4 , 0) ;
        build(a,1,low,n) ;
    }

    void build(ll a[] , int node , int low , int high)
    {
        if(low==high) lazy[node] = a[low] ;
        else
        {
            int mid = (low+high)>>1 , left = node<<1 , right = left|1 ;
            build(a,left,low,mid) , build(a,right,mid+1,high) ;
        }
    }

    void upd(int node , ll val)
    {
        lazy[node] += val ;
    }

    void shift(int node)
    {
        int left = node<<1 , right = left|1 ;
        upd(left,lazy[node]) , upd(right,lazy[node]) ;
        lazy[node] = 0 ;
    }
    void update(int node , int low , int high , int l , int r , ll val)
    {
        if(high<l || low>r) return ;
        if(l<=low && high<=r)
        {
            upd(node,val) ;
            return ;
        }
        shift(node) ;
        int mid = (low+high)>>1 , left = node<<1 , right = left|1 ;
        update(left,low,mid,l,r,val) , update(right,mid+1,high,l,r,val) ;
    }

    ll query(int node , int low , int high , int ind)
    {
        if(high<ind || low>ind) return 0 ;
        if(low==high && ind==low) return lazy[node] ;
        shift(node) ;
        int mid = (low+high)>>1 , left = node<<1 , right = left|1 ;
        return query(left,low,mid,ind) + query(right,mid+1,high,ind) ;
    }
};

int main()
{
    int n , q ;
    long long s , t , ans = 0 ;
    scanf("%d%d%lld%lld",&n,&q,&s,&t) ;
    long long a[n+1] ;
    for(int i = 0 ; i <= n ; ++i)
    {
        scanf("%lld",&a[i]) ;
        if(!i) continue ;
        if(a[i]>a[i-1]) ans -= (a[i]-a[i-1])*s ;
        else ans += (a[i-1]-a[i])*t ;
    }
    lazy_tree T(a,0,n) ;
    while(q--)
    {
        int l , r ;
        scanf("%d%d",&l,&r) ;
        long long x ;
        scanf("%lld",&x) ;
        a[l] = T.query(1,0,n,l) ;
        if(l)
        {
            a[l-1] = T.query(1,0,n,l-1) ;
            if(a[l]>a[l-1]) ans += (a[l]-a[l-1])*s ;
            else ans -= (a[l-1]-a[l])*t ;
        }
        a[r] = T.query(1,0,n,r) ;
        if(r<n)
        {
            a[r+1] = T.query(1,0,n,r+1) ;
            if(a[r+1]>a[r]) ans += (a[r+1]-a[r])*s ;
            else ans -= (a[r]-a[r+1])*t ;
        }
        T.update(1,0,n,l,r,x) ;
        a[l] = T.query(1,0,n,l) , a[r] = T.query(1,0,n,r) ;
        if(l)
        {
            if(a[l]>a[l-1]) ans -= (a[l]-a[l-1])*s ;
            else ans += (a[l-1]-a[l])*t ;
        }
        if(r<n)
        {
            if(a[r+1]>a[r]) ans -= (a[r+1]-a[r])*s ;
            else ans += (a[r]-a[r+1])*t ;
        }
        printf("%lld\n",ans) ;
    }
    return 0 ;
}

Compilation message (stderr)

foehn_phenomena.cpp: In function 'int main()':
foehn_phenomena.cpp:64:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   64 |     scanf("%d%d%lld%lld",&n,&q,&s,&t) ;
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
foehn_phenomena.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   68 |         scanf("%lld",&a[i]) ;
      |         ~~~~~^~~~~~~~~~~~~~
foehn_phenomena.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   77 |         scanf("%d%d",&l,&r) ;
      |         ~~~~~^~~~~~~~~~~~~~
foehn_phenomena.cpp:79:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   79 |         scanf("%lld",&x) ;
      |         ~~~~~^~~~~~~~~~~

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