Submission #535343

#	Time	Username	Problem	Language	Result	Execution time	Memory
535343		amunduzbaev	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	0 / 100	132 ms	3940 KiB

foehn_phenomena

#include "bits/stdc++.h"
using namespace std;
 
#define ar array
#define long long
const int N = 2e5 + 5;
struct ST{
	int tree[N];
	
	void add(int i, int v){ i++;
		for(;i<N;i+=(i&-i)) tree[i] += v;
	}
	
	int get(int i){ i++;
		int r=0;
		for(;i>0;i-=(i&-i)) r += tree[i];
		return r;
	}
}tree;

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, q, s, t; cin>>n>>q>>s>>t;
	vector<int> a(n + 1);
	for(int i=0;i<=n;i++) cin>>a[i];
	int res = 0;
	for(int i=1;i<=n;i++){
		if(a[i-1] < a[i]) res -= (a[i] - a[i-1]) * s;
		else res += (a[i-1] - a[i]) * t;
		tree.add(i, a[i]);
		tree.add(i+1, -a[i]);
	}
	
	auto check = [&](int i, int c){
		if(i <= 0 || i > n) return;
		int l = tree.get(i-1), r = tree.get(i);
		if(l < r) res -= (r - l) * s * c;
		else res += (l - r) * t * c;
	};
	
	while(q--){
		int l, r, x; cin>>l>>r>>x;
		check(l, -1), check(r+1, -1);
		tree.add(l, x);
		tree.add(r + 1, -x);
		check(l, 1), check(r+1, 1);
		cout<<res<<"\n";
	}
}

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