Submission #815809

#	Time	Username	Problem	Language	Result	Execution time	Memory
815809		OAleksa	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	193 ms	17212 KiB

foehn_phenomena

#include <bits/stdc++.h>
//#include "factories.h"
#define f first
#define s second
#define int long long
using namespace std; 
const int maxn = 2e5 + 69;
long long n, q, s, t, a[maxn], st[4 * maxn], f[maxn];

void upd(int v, int tl, int tr, int x, int d) {
	if(tl == tr)
		st[v] = d;
	else {
		int mid = (tl + tr) / 2;
		if(x <= mid)
			upd(v * 2, tl, mid, x, d);
		else
			upd(v * 2 + 1, mid + 1, tr, x, d);
		st[v] = st[v * 2] + st[v * 2 + 1];
	}
}

void add(int v, int d) {
	for(int i = v;i < maxn;i += (i & -i))
		f[i] += d;
}

int qry(int v) {
	int res = 0;
	for(int i = v;i >= 1;i -= (i & -i))
		res += f[i];
	return res;
}

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int tt = 1;
	//cin >> tt;
	while(tt--) {
		cin >> n >> q >> s >> t;
		for(int i = 0;i <= n;i++)
			cin >> a[i];
		for(int i = 1;i <= n;i++) {
			if(a[i] > a[i - 1]) 
				upd(1, 1, n, i, (a[i - 1] - a[i]) * s);
			else 
				upd(1, 1, n, i, (a[i - 1] - a[i]) * t);
		}
		for(int i = 1;i <= q;i++) {
			int l, r, x;
			cin >> l >> r >> x;
			add(l, x);
			add(r + 1, -x);
			int levi = a[l] + qry(l);
			int desni = a[r] + qry(r);
			int kurac = 0;
			int josjedankurac = 0;
			if(l > 1)
				kurac = a[l - 1] + qry(l - 1);
			if(r < n)
				josjedankurac = a[r + 1] + qry(r + 1);
			if(levi > kurac)
				upd(1, 1, n, l, (kurac - levi) * s);
			else
				upd(1, 1, n, l, (kurac - levi) * t);
			if(r < n) {
				if(josjedankurac > desni)
					upd(1, 1, n, r + 1, (desni - josjedankurac) * s);
				else
					upd(1, 1, n, r + 1, (desni - josjedankurac) * t);
			}
			cout << st[1] << "\n";
				
		}
	}
   return 0;
}

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