Submission #129521

#	Time	Username	Problem	Language	Result	Execution time	Memory
129521		khanh	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	0 / 100	1078 ms	17448 KiB

foehn_phenomena

#include<bits/stdc++.h>
#define int long long
#define inf 1e15 + 7
#define N 200005
using namespace std;

int n,q,up,down;
int arr[N] , lazy[N<<2] , node[N<<2];
int ans = 0;

void build_tree(int i,int l,int r) {
	if(l>r) return;
	if(l==r) {
		node[i] = arr[l];
		return;
	}
	int m = (l + r) / 2;
	build_tree(i<<1   , l , m);	m++;
	build_tree(i<<1|1 , m , r);
}

void true_val(int i,int l,int r) {
	if(l!=r) {
		node[i<<1] += lazy[i];
		lazy[i<<1] += lazy[i];
		
		node[i<<1|1] += lazy[i];
		lazy[i<<1|1] += lazy[i];
		lazy[i] = 0;
	}
}

void update(int i,int l,int r,int a,int b,int val) {
	if(l>r || b<l || r<a) return;
	if(a<=l && r<=b) {
		node[i] += val;
		lazy[i] += val;
		return;
	}
	true_val(i,l,r);
	int m = (l + r) / 2;
	update(i<<1   , l , m , a , b , val);	m++;
	update(i<<1|1 , m , r , a , b , val);
	node[i] = max(node[i<<1],node[i<<1|1]);
}

int get_max(int i,int l,int r,int a,int b) {
	true_val(i,l,r);
	if(l>r || b<l || r<a) return -inf;
	if(a<=l && r<=b) return node[i];
	int m = (l + r) / 2;
	return max(get_max(i<<1,l,m,a,b),get_max(i<<1|1,m+1,r,a,b));
}

main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n>>q>>down>>up;
	
	memset(lazy,0,sizeof(lazy));
	for(int i=0;i<=n;i++) cin>>arr[i];
	
	build_tree(1,1,n);
	
	for(int i=0;i<=n-1;i++) {
		if(arr[i] < arr[i+1]) ans -= down * abs(arr[i] - arr[i+1]);
		else ans += up * abs(arr[i] - arr[i+1]);
	}
	
	while(q--) {
		int l,r,x;	cin>>l>>r>>x;
		
		int MAX1 = (l==1 ? 0 : get_max(1,1,n,l-1,l-1));
		int MAX2 = get_max(1,1,n,l,l);
		
		if(MAX1 < MAX2 && MAX1 >= MAX2 + x) {
			ans += down * abs(MAX1 - MAX2);
			ans += up * abs(MAX1 - MAX2 - x);
		}
		else if(MAX1 < MAX2 && MAX1 < MAX2 + x) {
			ans += down * abs(MAX1 - MAX2);
			ans -= down * abs(MAX1 - MAX2 - x);
		}
		if(MAX1 >= MAX2 && MAX1 < MAX2 + x) {
			ans -= down * abs(MAX1 - MAX2 - x);
			ans -= up * abs(MAX1 - MAX2);
		}
		else if(MAX1 >= MAX2 && MAX1 >= MAX2 + x) {
			ans -= up * abs(MAX1 - MAX2);
			ans += up * abs(MAX1 - MAX2 - x);
		}
		
		if(r <= n - 1) {
			int MAX3 = get_max(1 , 1 , n , r , r);
			int MAX4 = get_max(1 , 1 , n , r + 1 , r + 1);
			
			if(MAX3 < MAX4 && MAX3 + x >= MAX4) {
				ans += down * abs(MAX3 - MAX4);
				ans += up * abs(MAX3 + x - MAX4);
			}
			else if(MAX3 < MAX4 && MAX3 + x < MAX4) {
				ans += down * abs(MAX3 - MAX4);
				ans -= down * abs(MAX3 + x - MAX4);
			}
			if(MAX3 >= MAX4 && MAX3 + x < MAX4) {
				ans -= up * abs(MAX3 - MAX4);
				ans -= down * (MAX3 + x - MAX4);
			}
			else if(MAX3 >= MAX4 && MAX3 + x >= MAX4) {
				ans -= up * abs(MAX3 - MAX4);
				ans += up * abs(MAX3 + x - MAX4);
			}
		}
		cout<<ans<<endl;
		update(1,1,n,l,r,x);
	}
}

Compilation message (stderr)

foehn_phenomena.cpp:55:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

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