oj.uz

Submission #129540

# Submission time Handle Problem Language Result Execution time Memory
129540 2019-07-12T13:05:59 Z khanh Foehn Phenomena (JOI17_foehn_phenomena) C++14
0 / 100
 1000 ms 19148 KB 
#include<bits/stdc++.h>
#define inf 1e15 + 7
#define N 200005
#define ll long long
using namespace std;

ll n,q,up,down;
ll arr[N] , lazy[4*N] , node[4*N];
ll ans = 0;

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

void true_val(ll i,ll l,ll r) {
	if(lazy[i]==0 || l > r) return;
	if(l!=r) {
		node[2*i] += lazy[i];
		lazy[2*i] += lazy[i];
		
		node[2*i+1] += lazy[i];
		lazy[2*i+1] += lazy[i];
	}
	lazy[i] = 0;
	return;
}

void update(ll i,ll l,ll r,ll a,ll b,ll 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);
	ll m = (l + r) / 2;
	update(2*i   , l , m , a , b , val);	m++;
	update(2*i+1 , m , r , a , b , val);
	node[i] = max(node[2*i],node[2*i+1]);
	return;
}

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

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin>>n>>q>>down>>up;
	
	memset(lazy,0,sizeof(lazy));
	for(ll i=0;i<=n;i++) cin>>arr[i];
	
	build_tree(1,1,n);
	
	for(ll 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--) {
		ll l,r,x;	cin>>l>>r>>x;
		if(l >= 1) {
			ll l1 = get_max(1,1,n,l-1,l-1);
			ll l2 = get_max(1,1,n,l,l);
			
			if(l1<l2) ans -= down * (l2-l1);
			
			else ans -= up * (l1-l2);
			
			if(l2+x>=l1) {
				ans += up * (l2+x-l1);
			}
			else {
				ans -= down * (l1-l2-x);
			}
		}
		if(r <= n - 1) {
			ll r1 = get_max(1,1,n,r,r);
			ll r2 = get_max(1,1,n,r+1,r+1);
			
			if(r1<r2) ans += down*(r2-r1);
			else ans -= up*(r1-r2);
			
			if(r1+x<r2) ans -= down*(r2-r1-x);
			else ans += up * (r1+x-r2);
		}
		cout<<ans<<endl;
		update(1,1,n,l,r,x);
	}
	return 0;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 6776 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1069 ms 19148 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 6776 KB Output isn't correct
2 Halted 0 ms 0 KB -