oj.uz

Submission #763111

# Submission time Handle Problem Language Result Execution time Memory
763111 2023-06-22T03:49:15 Z SanguineChameleon Wall (IOI14_wall) C++17
100 / 100
 569 ms 69528 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

const int inf = 1e9 + 20;
const int maxn = 2e6 + 20;
pair<int, int> tree[maxn * 4];

void build(int id, int lt, int rt) {
	if (lt == rt) {
		tree[id] = make_pair(0, 0);
		return;
	}
	tree[id] = make_pair(-inf, inf);
	int mt = (lt + rt) / 2;
	build(id * 2, lt, mt);
	build(id * 2 + 1, mt + 1, rt);
}

void update(int id, int lt, int rt) {
	if (tree[id].second < lt) {
		tree[id] = make_pair(lt, lt);
	}
	else if (tree[id].first > rt) {
		tree[id] = make_pair(rt, rt);
	}
	else {
		tree[id] = make_pair(max(lt, tree[id].first), min(rt, tree[id].second));
	}
}

void push(int id) {
	update(id * 2, tree[id].first, tree[id].second);
	update(id * 2 + 1, tree[id].first, tree[id].second);
	tree[id] = make_pair(-inf, inf);
}

void update(int id, int lt, int rt, int ql, int qr, int op, int h) {
	if (lt == ql && rt == qr) {
		if (op == 1) {
			update(id, h, inf);
		}
		else {
			update(id, -inf, h);
		}
		return;
	}
	push(id);
	int mt = (lt + rt) / 2;
	if (qr <= mt) {
		update(id * 2, lt, mt, ql, qr, op, h);
	}
	else if (ql >= mt + 1) {
		update(id * 2 + 1, mt + 1, rt, ql, qr, op, h);
	}
	else {
		update(id * 2, lt, mt, ql, mt, op, h);
		update(id * 2 + 1, mt + 1, rt, mt + 1, qr, op, h);
	}
}

int *finalHeight;

void push_all(int id, int lt, int rt) {
	if (lt == rt) {
		finalHeight[lt - 1] = tree[id].first;
		return;
	}
	push(id);
	int mt = (lt + rt) / 2;
	push_all(id * 2, lt, mt);
	push_all(id * 2 + 1, mt + 1, rt);
}

void buildWall(int n, int q, int op[], int left[], int right[], int height[], int _finalHeight[]) {
	finalHeight = _finalHeight;
	build(1, 1, n);
	for (int i = 0; i < q; i++) {
		update(1, 1, n, left[i] + 1, right[i] + 1, op[i], height[i]);
	}
	push_all(1, 1, n);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 5 ms 832 KB Output is correct
5 Correct 4 ms 724 KB Output is correct
6 Correct 4 ms 724 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 115 ms 9208 KB Output is correct
3 Correct 124 ms 5316 KB Output is correct
4 Correct 344 ms 11856 KB Output is correct
5 Correct 220 ms 12408 KB Output is correct
6 Correct 213 ms 12472 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 5 ms 800 KB Output is correct
5 Correct 4 ms 704 KB Output is correct
6 Correct 4 ms 724 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 110 ms 9240 KB Output is correct
9 Correct 129 ms 5280 KB Output is correct
10 Correct 378 ms 11924 KB Output is correct
11 Correct 213 ms 12364 KB Output is correct
12 Correct 221 ms 12432 KB Output is correct
13 Correct 1 ms 312 KB Output is correct
14 Correct 113 ms 9180 KB Output is correct
15 Correct 25 ms 2004 KB Output is correct
16 Correct 462 ms 12108 KB Output is correct
17 Correct 249 ms 12064 KB Output is correct
18 Correct 213 ms 12156 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 368 KB Output is correct
4 Correct 5 ms 724 KB Output is correct
5 Correct 4 ms 764 KB Output is correct
6 Correct 4 ms 724 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 111 ms 9252 KB Output is correct
9 Correct 122 ms 5252 KB Output is correct
10 Correct 341 ms 11928 KB Output is correct
11 Correct 227 ms 12312 KB Output is correct
12 Correct 212 ms 12396 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 141 ms 9220 KB Output is correct
15 Correct 25 ms 2004 KB Output is correct
16 Correct 444 ms 12112 KB Output is correct
17 Correct 222 ms 12108 KB Output is correct
18 Correct 217 ms 12136 KB Output is correct
19 Correct 529 ms 59940 KB Output is correct
20 Correct 518 ms 67008 KB Output is correct
21 Correct 569 ms 69468 KB Output is correct
22 Correct 518 ms 67020 KB Output is correct
23 Correct 534 ms 67016 KB Output is correct
24 Correct 553 ms 66980 KB Output is correct
25 Correct 561 ms 67004 KB Output is correct
26 Correct 524 ms 69452 KB Output is correct
27 Correct 524 ms 69528 KB Output is correct
28 Correct 527 ms 66892 KB Output is correct
29 Correct 519 ms 66972 KB Output is correct
30 Correct 531 ms 67000 KB Output is correct