oj.uz

Submission #779732

# Submission time Handle Problem Language Result Execution time Memory
779732 2023-07-11T18:00:48 Z zsombor Wall (IOI14_wall) C++17
0 / 100
 208 ms 111728 KB 
#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) {
	update_node(x, sgt[x / 2].MN, sgt[x / 2].MX);
}

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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 98036 KB Output is correct
2 Correct 42 ms 98148 KB Output is correct
3 Incorrect 39 ms 98204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 98096 KB Output is correct
2 Correct 162 ms 111728 KB Output is correct
3 Incorrect 208 ms 105336 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 98052 KB Output is correct
2 Correct 36 ms 98148 KB Output is correct
3 Incorrect 42 ms 98156 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 98044 KB Output is correct
2 Correct 37 ms 98256 KB Output is correct
3 Incorrect 44 ms 98176 KB Output isn't correct
4 Halted 0 ms 0 KB -