Submission #396540

#	Time	Username	Problem	Language	Result	Execution time	Memory
396540		giorgikob	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	808 ms	20296 KiB

foehn_phenomena

#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;

const int N = 2e5+50, mod = 1e9+7, K = 31;

int n,q,l,r,x;
ll L[N*4],R[N*4],A[N];
ll s,t;
ll sum[N*4],toadd[N*4];

inline void lazy(int node,int tl,int tr){
    int mid = (tl+tr)/2;
    int left = node*2;
    int right = node*2+1;
    //sum[left] += (mid-tl+1)*toadd[node];
    //sum[right] += (tr-mid)*toadd[node];
    L[left] += toadd[node]; R[left] += toadd[node];
    L[right] += toadd[node]; R[right] += toadd[node];
    toadd[left] += toadd[node];
    toadd[right] += toadd[node];
    toadd[node] = 0;
}

inline void merge(int node,int left,int right){
    L[node] = L[left];
    R[node] = R[right];
    ll x = 0, y = 0;
    if(R[left] < L[right]) x = s*(R[left]-L[right]); else
                           x = t*(R[left]-L[right]);
    sum[node] = sum[left]+sum[right]+x;
}

inline void upd(int node,int tl,int tr,int l,int r,int val){
    if(l > tr || tl > r) return ;
    if(tl == tr){
        L[node] += val;
        R[node] += val;
        return ;
    }
    if(l <= tl && tr <= r){
        //sum[node] += val*(tr-tl+1);
        toadd[node] += val;
        L[node] += val;
        R[node] += val;
        return ;
    }

    int mid = (tl+tr)/2;
    int left = node*2;
    int right = node*2+1;

    if(toadd[node]) lazy(node,tl,tr);

    upd(left,tl,mid,l,r,val);
    upd(right,mid+1,tr,l,r,val);

    merge(node,left,right);
}

inline void test_case(){

    cin >> n >> q >> s >> t;

    for(int i = 0; i <= n; i++){
        cin >> A[i];
        upd(1,0,n,i,i,A[i]);
    }

    while(q--){
        cin >> l >> r >> x;
        upd(1,0,n,l,r,x);
        cout << sum[1] << endl;
    }
}
 main(){
    ios::sync_with_stdio(0);

    int T = 1;
    //cin >> T;
    while(T--){
        test_case();
    }
}

Compilation message (stderr)

foehn_phenomena.cpp: In function 'void lazy(int, int, int)':
foehn_phenomena.cpp:16:9: warning: unused variable 'mid' [-Wunused-variable]
   16 |     int mid = (tl+tr)/2;
      |         ^~~
foehn_phenomena.cpp: In function 'void merge(int, int, int)':
foehn_phenomena.cpp:31:15: warning: unused variable 'y' [-Wunused-variable]
   31 |     ll x = 0, y = 0;
      |               ^
foehn_phenomena.cpp: At global scope:
foehn_phenomena.cpp:79:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   79 |  main(){
      |       ^

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