Submission #966544

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
966544	2024-04-20T03:19:47 Z	yellowtoad	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	30 / 100	31 ms	14160 KB

foehn_phenomena

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

long long n, q, s, t, a[100010], node[1000010], l, r, val, tmpl, tmpr, tnpl, tnpr, ans, tmp, tnp;

void update(int id, int x, int y) {
	if ((r < x) || (y < l)) return;
	if ((l <= x) && (y <= r)) {
		node[id] += val;
		return;
	}
	int mid = (x+y)/2;
	update(id*2,x,mid);
	update(id*2+1,mid+1,y);
}

long long find(int id, int x, int y, int pos) {
	if (x == y) return a[x]+node[id];
	int mid = (x+y)/2;
	node[id*2] += node[id];
	node[id*2+1] += node[id];
	node[id] = 0;
	if (pos <= mid) return find(id*2,x,mid,pos);
	else return find(id*2+1,mid+1,y,pos);
}

int main() {
	cin >> n >> q >> s >> t;
	for (int i = 0; i <= n; i++) {
		cin >> a[i];
		if (i > 0) {
			if (a[i] > a[i-1]) ans += s*(a[i-1]-a[i]);
			else ans += t*(a[i-1]-a[i]);
		}
	}
	while (q--) {
		cin >> l >> r >> val;
		if (r == n) tmpr = 0;
		else {
			tmp = find(1,0,n,r);
			tnp = find(1,0,n,r+1);
			if (tmp > tnp) tmpr = (tmp-tnp)*t;
			else tmpr = (tmp-tnp)*s;
		}
		tmp = find(1,0,n,l);
		tnp = find(1,0,n,l-1);
		if (tmp > tnp) tmpl = (tnp-tmp)*s;
		else tmpl = (tnp-tmp)*t;
		update(1,0,n);
		if (r == n) tnpr = 0;
		else {
			tmp = find(1,0,n,r);
			tnp = find(1,0,n,r+1);
			if (tmp > tnp) tnpr = (tmp-tnp)*t;
			else tnpr = (tmp-tnp)*s;
		}
		tmp = find(1,0,n,l);
		tnp = find(1,0,n,l-1);
		if (tmp > tnp) tnpl = (tnp-tmp)*s;
		else tnpl = (tnp-tmp)*t;
		ans += (tnpl-tmpl)+(tnpr-tmpr);
		cout << ans << endl;
	}
}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	2396 KB	Output is correct
2	Correct	6 ms	2652 KB	Output is correct
3	Correct	6 ms	2396 KB	Output is correct
4	Correct	6 ms	2396 KB	Output is correct
5	Correct	6 ms	2392 KB	Output is correct
6	Correct	6 ms	2396 KB	Output is correct
7	Correct	6 ms	2396 KB	Output is correct
8	Correct	6 ms	2392 KB	Output is correct
9	Correct	6 ms	2396 KB	Output is correct
10	Correct	7 ms	2588 KB	Output is correct
11	Correct	6 ms	2592 KB	Output is correct
12	Correct	6 ms	2648 KB	Output is correct
13	Correct	5 ms	2580 KB	Output is correct
14	Correct	5 ms	2396 KB	Output is correct
15	Correct	5 ms	2396 KB	Output is correct
16	Correct	5 ms	2396 KB	Output is correct
17	Correct	5 ms	2396 KB	Output is correct
18	Correct	5 ms	2588 KB	Output is correct
19	Correct	1 ms	2396 KB	Output is correct
20	Correct	0 ms	2496 KB	Output is correct
21	Correct	1 ms	2396 KB	Output is correct

Subtask #2

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	31 ms	14160 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #3

0 / 60.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	2396 KB	Output is correct
2	Correct	6 ms	2652 KB	Output is correct
3	Correct	6 ms	2396 KB	Output is correct
4	Correct	6 ms	2396 KB	Output is correct
5	Correct	6 ms	2392 KB	Output is correct
6	Correct	6 ms	2396 KB	Output is correct
7	Correct	6 ms	2396 KB	Output is correct
8	Correct	6 ms	2392 KB	Output is correct
9	Correct	6 ms	2396 KB	Output is correct
10	Correct	7 ms	2588 KB	Output is correct
11	Correct	6 ms	2592 KB	Output is correct
12	Correct	6 ms	2648 KB	Output is correct
13	Correct	5 ms	2580 KB	Output is correct
14	Correct	5 ms	2396 KB	Output is correct
15	Correct	5 ms	2396 KB	Output is correct
16	Correct	5 ms	2396 KB	Output is correct
17	Correct	5 ms	2396 KB	Output is correct
18	Correct	5 ms	2588 KB	Output is correct
19	Correct	1 ms	2396 KB	Output is correct
20	Correct	0 ms	2496 KB	Output is correct
21	Correct	1 ms	2396 KB	Output is correct
22	Runtime error	31 ms	14160 KB	Execution killed with signal 11
23	Halted	0 ms	0 KB	-