Submission #877259

#	Time	Username	Problem	Language	Result	Execution time	Memory
877259		hasan2006	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	459 ms	34260 KiB

foehn_phenomena

#include <bits/stdc++.h>

using namespace std;

#define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define rall(s) s.rbegin(),s.rend()
#define all(s) s.begin(),s.end()
#define pb push_back
#define se second
#define fi first
#define ll long long
#define ld long double
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define yes cout<<"yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define no cout<<"no\n"


const int N = 5e5 + 9 , mod = 1e9 + 7;
ll   a[N] = {}, b[N] , c[N] , d[N] , tree[2 * N] , lz[2 * N];


void lazzy(int i , int l , int r){
    tree[i] += lz[i] * (r - l + 1);
    lz[2 * i] += lz[i];
    lz[2 * i + 1] += lz[i];
    lz[i] = 0;
}

ll ind;
void get(int i , int l , int r , int x , int y ,int k){
    int m = (l + r) / 2;
    if(x > r || y < l){
        return;
    }
    lazzy(i , l,  r);
    if(l >= x && r <= y){
        tree[i] += (r - l + 1) * k;
        ind = tree[i];
        lz[2 * i] += k;
        lz[2 * i + 1] += k;
        return;
    }
    get(2 * i , l ,  m , x , y , k);
    get(2 * i + 1 , m + 1 , r , x , y , k);
    tree[i] = tree[2 * i] + tree[2 * i + 1];
}

void solve()
{
    ll q , i , j , m ,n, z ,s = 0 , f, l , r , k , x , y , mn  = 1e18 , mx = 0;
    cin>>n>>m>>x>>y;
    for(i = 0; i <= n; i++){
        cin>>a[i];
        if(i > 1)
            b[i - 1] = b[i - 2] , c[i - 1] = c[i - 2];
        if(i && a[i] >= a[i - 1]){
            s -= abs(a[i] - a[i - 1]) * x;
            b[i - 1]++;
        }else {
            s += abs(a[i] - a[i - 1]) * y;
            c[i - 1]++;
        }
    }
    while(m--){
        cin>>l>>r>>k;
        vector<ll>v;
        get(1 , 1 , n , l, r , k);
        if(l == 1)
            v.pb(0);
        else {
            get(1 , 1  , n , l - 1, l - 1 , 0);
            v.pb(ind + a[l - 1]);
        }
        get(1 , 1 , n , l, l , 0);
        v.pb(ind + a[l]);
        get(1 , 1 , n , r, r , 0);
        v.pb(ind + a[r]);
        if(r != n){
            get(1 , 1 , n , r + 1, r  + 1, 0);
            v.pb(ind + a[r + 1]);
        }
        if(v[0] <= (v[1] - k)){
            s += abs((v[1] - k) - v[0]) * x;
        }else {
            s -= abs((v[1] - k) - v[0]) * y;
        }
        if(v[0] <= v[1]){
            s -= abs(v[1] - v[0]) * x;
        }else {
            s += abs(v[1] - v[0]) * y;
        }
        if(r < n){
            if((v[2] - k) <= v[3]){
                s += abs(v[3] - (v[2] - k)) * x;
            }else {
                s -= abs(v[3] - (v[2] - k)) * y;
            }
            if(v[2] <= v[3]){
                s -= abs(v[3] - v[2]) * x;
            }else {
                s += abs(v[3] - v[2]) * y;
            }
        }
        cout<<s<<"\n";
    }
}

int main(){
    TL;
int t = 1;
//cin>>t;
while(t--)
     {
     solve();
     }
}
// Author : حسن

Compilation message (stderr)

foehn_phenomena.cpp: In function 'void solve()':
foehn_phenomena.cpp:53:8: warning: unused variable 'q' [-Wunused-variable]
   53 |     ll q , i , j , m ,n, z ,s = 0 , f, l , r , k , x , y , mn  = 1e18 , mx = 0;
      |        ^
foehn_phenomena.cpp:53:16: warning: unused variable 'j' [-Wunused-variable]
   53 |     ll q , i , j , m ,n, z ,s = 0 , f, l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                ^
foehn_phenomena.cpp:53:26: warning: unused variable 'z' [-Wunused-variable]
   53 |     ll q , i , j , m ,n, z ,s = 0 , f, l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                          ^
foehn_phenomena.cpp:53:37: warning: unused variable 'f' [-Wunused-variable]
   53 |     ll q , i , j , m ,n, z ,s = 0 , f, l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                     ^
foehn_phenomena.cpp:53:60: warning: unused variable 'mn' [-Wunused-variable]
   53 |     ll q , i , j , m ,n, z ,s = 0 , f, l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                                            ^~
foehn_phenomena.cpp:53:73: warning: unused variable 'mx' [-Wunused-variable]
   53 |     ll q , i , j , m ,n, z ,s = 0 , f, l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                                                         ^~

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