Submission #670922

#	Time	Username	Problem	Language	Result	Execution time	Memory
670922		Kahou	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	151 ms	7244 KiB

foehn_phenomena

/* In the name of God, aka Allah */
// let this be mytemp.cpp
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define endl '\n'
#define mk make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int N = 2e5 + 50;
ll n, q, s, t, a[N], sm[2];
ll fen[N];

ll get(int i) {
	ll out = 0;
	for (; i > 0; i -= i&-i) {
		out += fen[i];
	}
	return out;
}
void upd(int i, ll x) {
	for (; i <= n; i += i&-i) {
		fen[i] += x;
	}
}

void solve() {
	cin >> n >> q >> s >> t;
	s = -s;
	t = -t;
	for (int i = 0; i <= n; i++) {
		cin >> a[i];
		if (i > 0) {
			sm[(a[i] > a[i-1])] += a[i]-a[i-1];
			upd(i, a[i]-get(i-1));
		}
	}
	
	while (q--) {
		ll l, r, x;
		cin >> l >> r >> x;
		sm[(get(l) > get(l-1))] -= get(l)-get(l-1);
		if (r < n) sm[(get(r+1) > get(r))] -= get(r+1)-get(r);
		upd(l, x);
		upd(r+1, -x);
		sm[(get(l) > get(l-1))] += get(l)-get(l-1);
		if (r < n) sm[(get(r+1) > get(r))] += get(r+1)-get(r);
		
		cout << sm[0]*t + sm[1]*s << endl;
	}
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solve();
	return 0;
}

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