Submission #977483

#	Time	Username	Problem	Language	Result	Execution time	Memory
977483		Amaarsaa	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	669 ms	21680 KiB

foehn_phenomena

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
const int N = 4e5;
ll Has[4 * N + 2], S[4 * N + 2];
ll a[N + 2];
void PushDown(int p, int lo, int hi) {
	if (!Has[p] ) return ;
	ll mid = (lo + hi)/2;
	S[p] += (Has[p] * (hi - lo + 1));
	Has[2 * p] += Has[p];
	Has[2 * p + 1] += Has[p];
	Has[p] = 0;
}
void Update(ll p, ll lo, ll hi, ll l, ll r, ll x) {
	PushDown(p, lo, hi);
	if ( lo > r || l > hi) return ;
	if ( l <= lo && hi <= r) {
		Has[p] = x;
		return ;
	}
	ll mid = (lo + hi)/2;
	Update(2 * p , lo , mid, l, r, x);
	Update(2 * p + 1,  mid +1, hi, l, r, x);
	S[p] = S[2 * p] + S[2 * p + 1];
}
ll Find(ll p, ll lo, ll hi, ll x) {
	PushDown(p, lo, hi);
	if ( lo == hi) return S[p];
	ll mid = (lo + hi)/2;
	if ( x <= mid) return Find(2 * p, lo, mid, x);
	return Find(2 * p + 1, mid + 1, hi, x);
}
void Build(ll p, ll lo, ll hi) {
	if ( lo == hi) {
		S[p] = a[lo];
		return ;
	}
	ll mid = (lo + hi)/2;
	Build(2 * p , lo , mid);
	Build(2 * p + 1, mid + 1, hi);
	S[p] = S[2 * p] + S[2 * p + 1];
	
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	ll n, s, t, q, i, usult, buuralt,p, l, r, x;
	
	cin >> n >> q >> s >> t;
	
	
	usult = buuralt = 0;
	for (i =0; i <= n; i ++) {
		cin >> a[i];
		if ( i == 0) continue;
		if ( a[i] > a[i - 1]) usult += abs(a[i] - a[i - 1]);
		else buuralt += abs(a[i - 1] - a[i]);
	}
		p =(buuralt * t) - (s * usult);
	Build(1, 0, n);
	for (i = 1; i <= q; i ++) {
		cin >> l >> r >> x;
		a[l - 1] = Find(1, 0, n, l - 1);
		a[l] = Find(1, 0, n, l);
		a[r] = Find(1, 0, n, r);
		if ( r != n) a[r + 1] = Find(1, 0, n, r + 1);
		if ( a[l] > a[l - 1]) usult -= abs(a[l] - a[l- 1]);
		else buuralt -= abs(a[l] - a[l - 1]);
		if ( r != n) {
			if ( a[r] > a[r + 1]) buuralt -= abs(a[r] - a[r+1]);
			else usult -= abs(a[r] - a[r + 1]);
		}
		Update(1, 0, n, l, r, x);
		a[l - 1] = Find(1, 0, n, l - 1);
		a[l] = Find(1, 0, n, l);
		a[r] = Find(1, 0, n, r);
		if ( r != n) a[r + 1] = Find(1, 0, n, r + 1);
		if ( a[l] > a[l - 1]) usult += abs(a[l] - a[l- 1]);
		else buuralt += abs(a[l] - a[l - 1]);
		if ( r != n) {
			if ( a[r] > a[r + 1]) buuralt += abs(a[r] - a[r+1]);
			else usult += abs(a[r] - a[r + 1]);
		}
		p =(buuralt * t) - (s* usult);
		cout << p << endl;
	}
}

Compilation message (stderr)

foehn_phenomena.cpp: In function 'void PushDown(int, int, int)':
foehn_phenomena.cpp:10:5: warning: unused variable 'mid' [-Wunused-variable]
   10 |  ll mid = (lo + hi)/2;
      |     ^~~

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