Submission #777017

#	Time	Username	Problem	Language	Result	Execution time	Memory
777017		OrazB	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	363 ms	19756 KiB

foehn_phenomena

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_set;
//Dijkstra->set
//set.find_by_order(x) x-position value
//set.order_of_key(x) number of strictly less elements don't need *set.??
#define N 200005
#define wr cout << "Continue debugging\n";
#define all(x) (x).begin(), (x).end()
#define ll long long int
#define pii pair <int, int>
#define pb push_back
#define ff first
#define ss second

const ll inf = 1e18;
ll t[4*N], lazy[4*N], a[N];

void F(int l, int r, int idx){
	if (lazy[idx]){
		t[idx] += (r-l+1)*lazy[idx];
		if (l != r){
			lazy[idx*2] += lazy[idx];
			lazy[idx*2+1] += lazy[idx];
		}
		lazy[idx] = 0;
	}
}

void upd(int u, int v, int x, int l, int r, int idx){
	F(l, r, idx);
	if (l > v or r < u) return;
	if (u <= l and r <= v){
		t[idx] += (r-l+1)*x;
		if (l != r){
			lazy[idx*2] += x;
			lazy[idx*2+1] += x;
		}
		return;
	}
	int md = (l+r)/2;
	upd(u, v, x, l, md, idx*2);
	upd(u, v, x, md+1, r, idx*2+1);
}

ll find(int pos, int l, int r, int idx){
	F(l, r, idx);
	if (l == r) return t[idx];
	int md = (l+r)/2;
	if (pos <= md) return find(pos, l, md, idx*2);
	return find(pos, md+1, r, idx*2+1);
}
void build(int l, int r, int idx){
	if (l == r){
		t[idx] = a[l];
		return;
	}
	int md = (l+r)/2;
	build(l, md, idx*2);
	build(md+1, r, idx*2+1);
	t[idx] = t[idx*2]+t[idx*2+1];
}

int main ()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, q, s, t;
	ll ans = 0;
	cin >> n >> q >> s >> t;
	for (int i = 0; i <= n; i++){
		cin >> a[i];
		if (i and a[i] > a[i - 1]) ans -= s*(a[i]-a[i-1]);
		else if (i and a[i] <= a[i - 1]) ans += t*(a[i-1]-a[i]);
	}
	build(1, n, 1);
	while(q--){
		int l, r, x;
		cin >> l >> r >> x;
		ll a2 = find(l, 1, n, 1), a1 = (l == 1 ? 0 : find(l-1, 1, n, 1));
		ll b1 = find(r, 1, n, 1), b2 = (r == n ? inf : find(r+1, 1, n, 1));
		ans -= (a1 < a2 ? -s : t)*abs(a1-a2);
		if (b2 != inf) ans -= (b1 < b2 ? -s : t)*abs(b1-b2);
		upd(l, r, x, 1, n, 1);
		a2 = find(l, 1, n, 1); 
		a1 = (l == 1 ? 0 : find(l-1, 1, n, 1));
		b1 = find(r, 1, n, 1); 
		b2 = (r == n ? inf : find(r+1, 1, n, 1));
		ans += (a1 < a2 ? -s : t)*abs(a1-a2);
		if (b2 != inf) ans += (b1 < b2 ? -s : t)*abs(b1-b2);
		// cout << a1 << " " << a2 << "   " << b1 << " " << b2 << "   " << ans << '\n';
		assert(ans <= 1e18);
		cout << ans << '\n';
	}
}	

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