Submission #783597

#	Time	Username	Problem	Language	Result	Execution time	Memory
783597		Owen11	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	395 ms	11320 KiB

foehn_phenomena

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

# define int long long
# define fir first
# define sec second
# define pb push_back

const int cnst = 2e5+5;
bool mutipletestcase = 0;
//bool debug = false;

int n, q, s, t; 
int all[cnst]; 
int arr[cnst];
int posi[cnst*4];
int lazy[cnst*4];

int merge(int a, int b) {
	return a+b;
}

void build(int a, int b, int id) {
	if(a == b) {
		if(arr[a] < 0) posi[id] = s*abs(arr[a]);
		else posi[id] = t*abs(arr[a]);
		return;
	}
	int mid = (a+b)/2;
	build(a, mid, id*2);
	build(mid+1, b, id*2+1);
	posi[id] = merge(posi[id*2], posi[id*2+1]);
}

void update(int a, int b, int id, int pos, int val) {
	if(pos > b || pos < a) return;
	// cerr << a << " " << b << " " << id << " " << pos << " " << val << endl;
	if(a == pos && b == pos) {
		if(arr[a] < 0) posi[id] = s*abs(arr[a]);
		else posi[id] = t*abs(arr[a]);
		return;
	}
	int mid =(a+b)/2;
	if(pos <= mid) update(a, mid, id*2, pos, val);
	else update(mid+1, b, id*2+1, pos, val);
	posi[id] = merge(posi[id*2], posi[id*2+1]);
}

int get(int a, int b, int id, int from, int to) {
	if(to < a || from > b) return 0;
	if(from <= a && b <= to) return posi[id];
	int mid = (a+b)/2;
	return merge(get(a, mid, id*2, from, to), get(mid+1, b, id*2+1, from, to));
}


void solve() {
	cin >> n >> q >> s >> t; s *= -1;

	// all[0] = 0;

	for(int i = 0 ; i<=n; i++) cin >> all[i];
	for(int i = 1; i<=n; i++) arr[i] = all[i-1]-all[i];

	build(1, n, 1);
	// cerr << get(1, n, 1, 1, n) << endl;
	// for(int i = 1; i<=n; i++) cerr << arr[i] << " "; cerr << endl;
	// for(int i = 1; i<=n; i++) cerr << get(1, n, 1, i, i) << " "; cerr << endl; cerr << endl;

	while(q--) {
		int x, y, z; cin >> x >> y >> z;
		arr[x] -= z;
		arr[y+1] += z;

		update(1, n, 1, x, 0);
		// update(1, n, 1, y, 0);
		update(1, n, 1, y+1, 0);

		// for(int i = 1; i<=n; i++) cerr << arr[i] << " "; cerr << endl;
		// for(int i = 1; i<=n; i++) cerr << get(1, n, 1, i, i) << " "; cerr << endl; cerr << endl;

		cout << get(1, n, 1, 1, n) << endl;
	}
}

signed main() {
	ios_base::sync_with_stdio(false);
	int t = 1;
	if(mutipletestcase) cin >> t; 
	while(t--) solve();
}

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