Submission #1272136

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272136		thuhienne	Foehn Phenomena (JOI17_foehn_phenomena)	C++20	100 / 100	231 ms	21408 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';
	}
}

/*
  Thuong em khi mua thu
  Thuong em sang mua ha
  Thuong em bang qua mua dong,gui gio xuan om em vao long
  Thuong em bao mua mua
  Tham thuong luon bao mua nang
  Thuong yeu em khong doi thay,gio mat em tim toi hao gay ):
*/

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