Submission #1272786

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272786		nthvn	Foehn Phenomena (JOI17_foehn_phenomena)	C++20	100 / 100	209 ms	21360 KiB

foehn_phenomena

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

int n,q,s,t,altitude[200009];

struct node {
	long long front,back,temp;
};

node st[200009 * 4];
long long lazy[200009 * 4];

long long cost(long long ai,long long ai1) {
	if (ai < ai1) return s * (ai - ai1);
	return t * (ai - ai1);
}

void build(int id,int l,int r) {
	if (l == r) {
		st[id] = {altitude[l],altitude[r],0};
		return;
	}
	int mid = (l + r) >> 1;
	build(id*2,l,mid);
	build(id*2+1,mid+1,r);
	st[id] = {st[id*2].front,st[id*2+1].back,
				st[id*2].temp + st[id*2+1].temp + cost(st[id*2].back,st[id*2+1].front)};
}
void changenode(int id,long long val) {
	st[id].front += val;
	st[id].back += val;
	lazy[id] += val;
}
void push_down(int id) {
	changenode(id*2,lazy[id]);
	changenode(id*2+1,lazy[id]);
	lazy[id] = 0;
}
void update(int id,int l,int r,int u,int v,int val) {
	if (l > v || r < u) return;
	if (l >= u && r <= v) {
		changenode(id,val);
		return;
	}
	int mid = (l + r) >> 1;
	push_down(id);
	update(id*2,l,mid,u,v,val);
	update(id*2+1,mid+1,r,u,v,val);
	st[id] = {st[id*2].front,st[id*2+1].back,
				st[id*2].temp + st[id*2+1].temp + cost(st[id*2].back,st[id*2+1].front)};
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(nullptr);
//  freopen(".inp","r",stdin);
//  freopen(".out","w",stdout);
	cin >> n >> q >> s >> t;
	for (int i = 0;i <= n;i++) cin >> altitude[i];
	build(1,1,n);
	while (q--) {
		int l,r,x;cin >> l >> r >> x;
		update(1,1,n,l,r,x);
		cout << st[1].temp + cost(0,st[1].front) << '\n';
	}
}

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