Submission #900782

#	Time	Username	Problem	Language	Result	Execution time	Memory
900782		Isam	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	30 / 100	309 ms	21592 KiB

foehn_phenomena

#include<bits/stdc++.h>
using namespace std;
constexpr int sz = 200005;

int N, Q, S, T, A[sz];
long long sm, Temp[sz], tree[sz << 2], lazy[sz << 2];

inline void build(int l, int r, int node){
	if(l == r){
		tree[node] = A[l];
		return;
	}
	int mid = l + ((r - l) >> 1);
	build(l, mid, node << 1);
	build(mid + 1, r, node << 1 | 1);
	tree[node] = tree[node << 1] + tree[node << 1 | 1];
	return;
}

inline void relax(int node, int l, int r){
	if(l != r){
		lazy[node << 1] += lazy[node];
		lazy[node << 1 | 1] += lazy[node];
	}
	tree[node] += 1ll * (r - l + 1) * lazy[node];
	lazy[node] = 0ll;
	return;
}

inline void update(int l, int r, int node, int L, int R, int val){
	if(lazy[node]) relax(node, l, r);
	if(l > R || r < L || r < l) return;
	if(l >= L && r <= R){
		lazy[node] += val;
		relax(node, l, r);
		return;
	}
	int mid = l + ((r - l) >> 1);
	update(l, mid, node << 1, L, R, val);
	update(mid + 1, r, node << 1 | 1, L, R, val);
	tree[node] = tree[node << 1] + tree[node << 1 | 1];
	return;
}

long long get_ans(int l, int r, int node, int L, int R){
	if(l > R || r < L || r < l) return 0ll;
	if(lazy[node]) relax(node, l, r);
	if(l >= L && r <= R) return tree[node];
	int mid = l + ((r - l) >> 1);
	return get_ans(l, mid, node << 1, L, R) + get_ans(mid + 1, r, node << 1 | 1, L, R);
}

signed main(){
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> N >> Q >> S >> T;
	for(register int i = 0; i <= N; ++i) cin >> A[i];
	build(1, N, 1);
	function<void(int, int)> Update = [&](int pos, int val){
		if(!(pos >= 1 && pos <= N)) return;
		sm -= Temp[pos];
		if(val < 0){
			Temp[pos] = 1ll * val * S;
		}else{
			Temp[pos] = 1ll * val * T;
		}
		sm += Temp[pos];
	};
	for(register int i = 1; i <= N; ++i) Update(i, A[i - 1] - A[i]);
	int L, R, X;
	while(Q--){
		cin >> L >> R>> X;
		update(1, N, 1, L, R, X);
		Update(L, get_ans(1, N, 1, L - 1, L - 1) - get_ans(1, N, 1, L, L));
		Update(R + 1, get_ans(1, N, 1, R, R) - get_ans(1, N, 1, R + 1, R + 1));
		cout << sm << '\n';
	}
	return 0;
}

Compilation message (stderr)

foehn_phenomena.cpp: In function 'int main()':
foehn_phenomena.cpp:56:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   56 |  for(register int i = 0; i <= N; ++i) cin >> A[i];
      |                   ^
foehn_phenomena.cpp:68:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   68 |  for(register int i = 1; i <= N; ++i) Update(i, A[i - 1] - A[i]);
      |                   ^

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