제출 #815804

#제출 시각아이디문제언어결과실행 시간메모리
815804OAleksaFoehn Phenomena (JOI17_foehn_phenomena)C++17
30 / 100
481 ms18996 KiB
#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], l[4 * maxn], stb[4 * maxn];

void push(int v) {
	stb[v] += l[v];
	l[v * 2] += l[v];
	l[v * 2 + 1] += l[v];
	l[v] = 0;
}

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 upd(int v, int tl, int tr, int L, int R, int x) {
	push(v);                                                                                      
	if(tl > R || tr < L)
		return;
	else if(tl >= L && tr <= R) 
		l[v] += x;
	else {
		int mid = (tl + tr) / 2;
		upd(v * 2, tl, mid, L, R, x);
		upd(v * 2 + 1, mid + 1, tr, L, R, x);
	}
}

long long qry(int v, int tl, int tr, int x) {
	push(v);
	if(tl == tr)
		return stb[v];
	else {
		int mid = (tl + tr) / 2;
		if(x <= mid)
			return qry(v * 2, tl, mid, x);
		else
			return qry(v * 2 + 1, mid + 1, tr, x);
	}
}

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++)
			upd(1, 1, n, i, i, 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;
			upd(1, 1, n, l, r, x);
			int levi = qry(1, 1, n, l);
			int desni = qry(1, 1, n, r);
			int kurac = 0;
			int josjedankurac = desni;
			if(l > 1)
				kurac = qry(1, 1, n, l - 1);
			if(r < n)
				josjedankurac = qry(1, 1, n, 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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...