Submission #779745

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
779745	2023-07-11T18:25:48 Z	zsombor	Wall (IOI14_wall)	C++17	8 / 100	3000 ms	111804 KB

wall

#include <iostream>
#include <vector>
#include "wall.h"
using namespace std;

struct node {
	int L, M, R, MN, MX;
	node() { MN = 0; MX = 1e5; }
};

vector <node> sgt(5e6, node());

void build_sgt(int x, int l, int r) {
	sgt[x].L = l;
	sgt[x].M = (l + r) / 2;
	sgt[x].R = r;
	if (r - l == 1) { sgt[x].MX = 0; return; }
	build_sgt(2 * x, l, (l + r) / 2);
	build_sgt(2 * x + 1, (l + r) / 2, r);
}

void update_node(int x, int mn, int mx) {
	if (mx < sgt[x].MN) { sgt[x].MN = sgt[x].MX = mx; return; }
	if (mn > sgt[x].MX) { sgt[x].MN = sgt[x].MX = mn; return; }
	sgt[x].MN = max(sgt[x].MN, mn);
	sgt[x].MX = min(sgt[x].MX, mx);
}

void push_down(int x) {
	if (sgt[x].R - sgt[x].L == 1) return;
	update_node(2 * x, sgt[x].MN, sgt[x].MX);
	update_node(2 * x + 1, sgt[x].MN, sgt[x].MX);
	sgt[x].L = 0;
	sgt[x].R = 1e5;
}

void update(int x, int l, int r, int mn, int mx) {
	push_down(x);
	if (r <= sgt[x].L || sgt[x].R <= l) return;
	if (l <= sgt[x].L && sgt[x].R <= r) { update_node(x, mn, mx); return; }
	update(2 * x, l, r, mn, mx);
	update(2 * x + 1, l, r, mn, mx);
}

int query(int x,int i) {
	push_down(x);
	if (sgt[x].R - sgt[x].L == 1) return sgt[x].MN;
	return (i < sgt[x].M ? query(2 * x, i) : query(2 * x + 1, i));
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
	build_sgt(1, 0, n);
	for (int i = 0; i < k; i++) {
		if (op[i] == 1) update(1, left[i], right[i] + 1, height[i], 1e5);
		else update(1, left[i], right[i] + 1, 0, height[i]);
	}
	for (int i = 0; i < n; i++) finalHeight[i] = query(1, i);
}

Subtask #1

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	44 ms	98132 KB	Output is correct
2	Correct	41 ms	98200 KB	Output is correct
3	Correct	46 ms	98100 KB	Output is correct
4	Correct	746 ms	98336 KB	Output is correct
5	Correct	707 ms	98336 KB	Output is correct
6	Correct	737 ms	98344 KB	Output is correct

Subtask #2

0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	38 ms	98124 KB	Output is correct
2	Correct	154 ms	106340 KB	Output is correct
3	Execution timed out	3056 ms	101836 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

Subtask #3

0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	38 ms	98124 KB	Output is correct
2	Correct	44 ms	98264 KB	Output is correct
3	Correct	56 ms	98156 KB	Output is correct
4	Correct	745 ms	98332 KB	Output is correct
5	Correct	712 ms	98340 KB	Output is correct
6	Correct	719 ms	98336 KB	Output is correct
7	Correct	40 ms	98040 KB	Output is correct
8	Correct	152 ms	111736 KB	Output is correct
9	Execution timed out	3067 ms	105164 KB	Time limit exceeded
10	Halted	0 ms	0 KB	-

Subtask #4

0 / 39.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	40 ms	98020 KB	Output is correct
2	Correct	41 ms	98252 KB	Output is correct
3	Correct	47 ms	98112 KB	Output is correct
4	Correct	703 ms	98344 KB	Output is correct
5	Correct	723 ms	98344 KB	Output is correct
6	Correct	720 ms	98344 KB	Output is correct
7	Correct	40 ms	98100 KB	Output is correct
8	Correct	167 ms	111804 KB	Output is correct
9	Execution timed out	3056 ms	105188 KB	Time limit exceeded
10	Halted	0 ms	0 KB	-