oj.uz

Submission #763110

# Submission time Handle Problem Language Result Execution time Memory
763110 2023-06-22T03:48:25 Z SanguineChameleon Wall (IOI14_wall) C++17
61 / 100
 461 ms 87124 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

const int inf = 1e9 + 20;
const int maxn = 1e6 + 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 2 ms 340 KB Output is correct
4 Correct 7 ms 828 KB Output is correct
5 Correct 4 ms 700 KB Output is correct
6 Correct 4 ms 832 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 109 ms 13920 KB Output is correct
3 Correct 126 ms 7884 KB Output is correct
4 Correct 363 ms 20360 KB Output is correct
5 Correct 214 ms 21372 KB Output is correct
6 Correct 209 ms 19808 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 2 ms 340 KB Output is correct
4 Correct 5 ms 804 KB Output is correct
5 Correct 4 ms 724 KB Output is correct
6 Correct 4 ms 700 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 111 ms 13824 KB Output is correct
9 Correct 134 ms 7868 KB Output is correct
10 Correct 346 ms 20320 KB Output is correct
11 Correct 229 ms 21364 KB Output is correct
12 Correct 210 ms 19852 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 112 ms 13932 KB Output is correct
15 Correct 25 ms 1976 KB Output is correct
16 Correct 450 ms 20560 KB Output is correct
17 Correct 224 ms 20024 KB Output is correct
18 Correct 218 ms 19988 KB Output is correct

Subtask #4
0 / 39.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 2 ms 340 KB Output is correct
4 Correct 5 ms 832 KB Output is correct
5 Correct 4 ms 764 KB Output is correct
6 Correct 4 ms 724 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 112 ms 13828 KB Output is correct
9 Correct 128 ms 7948 KB Output is correct
10 Correct 341 ms 20316 KB Output is correct
11 Correct 214 ms 21320 KB Output is correct
12 Correct 211 ms 19744 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 114 ms 13928 KB Output is correct
15 Correct 29 ms 1992 KB Output is correct
16 Correct 461 ms 20568 KB Output is correct
17 Correct 220 ms 20024 KB Output is correct
18 Correct 218 ms 19984 KB Output is correct
19 Runtime error 230 ms 87124 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -