Submission #382855

#	Time	Username	Problem	Language	Result	Execution time	Memory
382855		ritul_kr_singh	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	490 ms	15748 KiB

foehn_phenomena

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << " " <<
#define nl << "\n"

struct segtree{
	int sz = 1;
	vector<int> a;
	segtree(vector<int> &v){
		while(sz < (int)v.size()) sz *= 2;
		a.assign(2*sz, 0);
		build(v, 0, 0, sz);
	}
	void build(vector<int> &v, int x, int lx, int rx){
		if(rx-lx==1){
			if(lx<(int)v.size()) a[x] = v[lx];
			return;
		}
		int mx = (lx+rx)/2;
		build(v, x+x+1, lx, mx);
		build(v, x+x+2, mx, rx);
	}
	void update(int l, int r, int val, int x, int lx, int rx){
		if(rx<=l or r<=lx) return;
		if(l<=lx and rx<=r) return void(a[x] += val);
		int mx = (lx+rx)/2;
		update(l, r, val, x+x+1, lx, mx);
		update(l, r, val, x+x+2, mx, rx);
	}
	void update(int l, int r, int val){ update(l, r+1, val, 0, 0, sz); }
	int get(int i, int x, int lx, int rx){
		if(rx-lx==1) return a[x];
		int mx = (lx+rx)/2;
		if(i<mx) return a[x] + get(i, x+x+1, lx, mx);
		else return a[x] + get(i, x+x+2, mx, rx);
	}
	int get(int i){ return get(i, 0, 0, sz); }
};

int n, q, s, t;

int f(int x, int y){
	return (x-y)*((x<y) ? s : t);
}

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> q >> s >> t;
	vector<int> a(n+1);
	for(int &i : a) cin >> i;
	int res = 0;
	for(int i=0; i<n; ++i) res += f(a[i], a[i+1]);

	segtree st(a);
	while(q--){
		int l, r, x; cin >> l >> r >> x;
		res -= f(st.get(l-1), st.get(l));
		if(r<n) res -= f(st.get(r), st.get(r+1));

		st.update(l, r, x);
		res += f(st.get(l-1), st.get(l));
		if(r<n) res += f(st.get(r), st.get(r+1));
		cout << res nl;
	}
}

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