Submission #915597

#	Time	Username	Problem	Language	Result	Execution time	Memory
915597		Minbaev	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	533 ms	34616 KiB

foehn_phenomena

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pii pair<int,int>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define int long long
#define f first
#define s second
#define pii pair<int,int>
template<class T>bool umax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T>bool umin(T &a,T b){if(b<a){a=b;return true;}return false;}
typedef tree<int, null_type, less_equal<int>, rb_tree_tag,
	tree_order_statistics_node_update> ordered_set;
const int mod= 1e17 +7;
const int N=2e5 + 5	;
const int inf = 1e17 + 7;

int binpow (int a, int n) {
	if (n == 0)
		return 1;
	if (n % 2 == 1)
		return binpow (a, n-1) * a;
	else {
		int b = binpow (a, n/2);
		return b * b;
	}
}
int n,m,k,q;
int t[N * 4], bn[N * 4], h[N * 4], hi[N * 4];

void push(int tl, int tr, int v){
	
	if(tl != tr){
		bn[v * 2] += bn[v];
		bn[v * 2 + 1] += bn[v];
	}
	t[v] += bn[v];
	bn[v] = 0;
}

void update(int tl,int tr,int v,int l,int r,int val){
	push(tl,tr,v);
	if(r<tl||tr<l)return;
	
	if(l<=tl&&tr<=r){
		bn[v] += val;
		push(tl,tr,v);
		//~ cout<<t[v]<<"\n";
		return;
	}
	
	int tm = (tl + tr) / 2;
	
	update(tl,tm,v * 2,l,r,val);
	update(tm+1,tr,v * 2 + 1,l,r,val);
	
}

int get(int tl,int tr, int v,int pos){
	push(tl,tr,v);
	if(tl == tr){
		//~ cout<<v<<"\n";
		return t[v];
	}
	int tm = (tl + tr)/2;
	
	if(pos <= tm)return get(tl,tm,v * 2,pos);
	else return get(tm+1,tr,v * 2 + 1,pos);
	
}
//-----------------------------------------------------------------------------------------------------------------------------------------------------
void push1(int tl, int tr, int v){
	
	if(tl != tr){
		hi[v * 2] += hi[v];
		hi[v * 2 + 1] += hi[v];
	}
	h[v] += hi[v];
	hi[v] = 0;
}

void update1(int tl,int tr,int v,int l,int r,int val){
	push1(tl,tr,v);
	if(r<tl||tr<l)return;
	
	if(l<=tl&&tr<=r){
		hi[v] += val;
		push1(tl,tr,v);
		return;
	}
	
	int tm = (tl + tr) / 2;
	
	update1(tl,tm,v * 2,l,r,val);
	update1(tm+1,tr,v * 2 + 1,l,r,val);
	
}

int get1(int tl,int tr, int v,int pos){
	push1(tl,tr,v);
	if(tl == tr){
		return h[v];
	}
	int tm = (tl + tr)/2;
	
	if(pos <= tm)return get1(tl,tm,v * 2,pos);
	else return get1(tm+1,tr,v * 2 + 1,pos);
	
}


void solve(){
	
	cin >> n >> q >> m >> k;
	
	vector<int>v(n + 1);
	
	for(int i = 0;i<=n;i++){
		cin>>v[i];
	}
	int last = 0;
	for(int i = 1;i<=n;i++){
		
		if(v[i - 1] >= v[i]){
			last += (v[i - 1] - v[i]) * k;
		}
		else{
			last -= (v[i] - v[i - 1]) * m;	
		}
		
		update(1,n,1,i,i,last);
		//~ cout<<get(1,n,1,i)<<"\n";
	}
	
	for(int i = 1;i<=n;i++){
		update1(1,n,1,i,i,v[i]);
	}
	//~ cout<<get(1,n,1,n)<<"\n";
	
	while(q--){
		int l,r,val;
		
		cin>>l>>r>>val;
		
		int h1 = 0; if(l > 1)h1 = get1(1,n,1,l - 1);
		int h2 = get1(1,n,1,l);
		
		int dif = 0;
		if(h1 > h2)dif += (h1 - h2) * k;
		else dif -= (h2 - h1) * m;

		
		int dif1 = 0; h2 += val;
		if(h1 > h2)dif1 += (h1 - h2) * k;
		else dif1 -= (h2 - h1) * m;
		
		int sum1 = dif1 - dif;
		//~ cout<<h1<<" "<<h2<<" "<<dif<<" "<<dif1<<"\n";
		if(r < n){
			h1 = get1(1,n,1,r);
			h2 = get1(1,n,1,r + 1);
			
			 dif = 0;
			if(h1 > h2)dif += (h1 - h2) * k;
			else dif -= (h2 - h1) * m;

		
			 dif1 = 0; h1 += val;
			if(h1 > h2)dif1 += (h1 - h2) * k;
			else dif1 -= (h2 - h1) * m;
			
			update(1,n,1,r + 1,n,dif1 - dif);
		}
		update(1,n,1,l,n,sum1);
		update1(1,n,1,l,r,val);
		cout<<get(1,n,1,n)<<"\n";
	}
	
	
	
}

 signed main()
{
//	freopen("seq.in", "r", stdin);
//  freopen("seq.out", "w", stdout);
	ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
	int tt=1;//cin>>tt>>n;
	while(tt--)solve();

}

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