Submission #670926

#	Time	Username	Problem	Language	Result	Execution time	Memory
670926		Makarooni	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	506 ms	13376 KiB

foehn_phenomena

/* IN THE NAME OF GOD */
/* |\/| /-\ |\| | |\/| /-\ */

#include "bits/stdc++.h"
using namespace std;

#define sz(x) (int)x.size()
#define endl '\n'
#define pb push_back
#define all(x) x.begin(), x.end()
#define F first
#define S second
#define mr make_pair
//#define int long long
#define pii pair<int, int>
typedef long double ld;
typedef long long ll;

mt19937 rng (chrono::high_resolution_clock::now().time_since_epoch().count());

const int N = 2e5 + 10;
const ll MOD = 1e9 + 7;
const int inf = 1e9;
const ll INF = 2e18;

ll seg[N * 4], lz[N * 4], ans;
int a[N];

void bulid(int id, int s, int e){
	if(s == e){
		seg[id] = a[s];
		return;
	}
	int mid = (s + e) / 2;
	bulid(id * 2, s, mid);
	bulid(id * 2 + 1, mid + 1, e);
}

void shift(int id, int s, int e){
	if(s == e)
		return;
	int mid = (s + e) / 2;
	seg[id * 2] += lz[id] * (mid - s + 1);
	seg[id * 2 + 1] += lz[id] * (e - mid);
	lz[id * 2] += lz[id];
	lz[id * 2 + 1] += lz[id];
	lz[id] = 0;
}

void upd(int id, int s, int e, int l, int r, int x){
	shift(id, s, e);
	if(s > r || e < l)
		return;
	if(l <= s && e <= r){
		seg[id] += (s - e + 1) * x;
		lz[id] += x;
		return;
	}
	int mid = (s + e) / 2;
	upd(id * 2, s, mid, l, r, x);
	upd(id * 2 + 1, mid + 1, e, l, r, x);
	seg[id] = seg[id * 2] + seg[id * 2 + 1];
}

ll get(int id, int s, int e, int p){
	shift(id, s, e);
	if(s == e && s == p)
		return seg[id];
	if(s > p || e < p)
		return 0;
	int mid = (s + e) / 2;
	return get(id * 2, s, mid, p) + get(id * 2 + 1, mid + 1, e, p);
}

int32_t main(){
	ios_base:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n, q;
	ll s, t;
	cin >> n >> q >> s >> t;
	for(int i = 0; i <= n; i++)
		cin >> a[i];
	bulid(1, 1, n);
	for(int i = 1; i <= n; i++){
		if(a[i] > a[i - 1])
			ans += -s * (a[i] - a[i - 1]);
		else
			ans += t * (a[i - 1] - a[i]);
	}
	int l, r, x;
	while(q--){
		cin >> l >> r >> x;
		ll L = get(1, 1, n, l), Lm = get(1, 1, n, l - 1), R = get(1, 1, n, r), Rp = get(1, 1, n, r + 1);
		//cout << Lm << " " << L << " " << R << " " << Rp << endl;
		if(L > Lm)
			ans -= -s * (L - Lm);
		else
			ans -= t * (Lm - L);
		if(Rp > R && r != n)
			ans -= -s * (Rp - R);
		else if(r != n)
			ans -= t * (R - Rp);
		upd(1, 1, n, l, r, x);
		L += x;
		R += x;
		if(L > Lm)
			ans += -s * (L - Lm);
		else
			ans += t * (Lm - L);
		if(Rp > R && r != n)
			ans += -s * (Rp - R);
		else if(r != n)
			ans += t * (R - Rp);
		cout << ans << endl;
	}
}

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