oj.uz

Submission #743635

# Submission time Handle Problem Language Result Execution time Memory
743635 2023-05-17T14:57:26 Z josanneo22 Wall (IOI14_wall) C++17
100 / 100
 677 ms 77344 KB 
#include <bits/stdc++.h>
#include<unordered_map>
#include<algorithm>
using namespace std;

#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second 
struct node {
	int mx = 0, mn = 0;
};
node tree[2 * (1 << 22) + 20];
vector<int> ans(2000005);
void lazy(int pos) {
	tree[2 * pos].mn = min(tree[2 * pos].mn, tree[pos].mn);
	tree[2 * pos].mn = max(tree[2 * pos].mn, tree[pos].mx);
	tree[2 * pos].mx = min(tree[2 * pos].mx, tree[pos].mn);
	tree[2 * pos].mx = max(tree[2 * pos].mx, tree[pos].mx);
	tree[2 * pos + 1].mn = min(tree[2 * pos + 1].mn, tree[pos].mn);
	tree[2 * pos + 1].mn = max(tree[2 * pos + 1].mn, tree[pos].mx);
	tree[2 * pos + 1].mx = min(tree[2 * pos + 1].mx, tree[pos].mn);
	tree[2 * pos + 1].mx = max(tree[2 * pos + 1].mx, tree[pos].mx);
	return;
}

void update(int tree_index, int tl, int tr, int l, int r, int type, int heigh) {
	if (tr<l || tl>r) return;
	if (l <= tl && tr <= r) {
		if (type == 1) {
			tree[tree_index].mn = max(tree[tree_index].mn, heigh);
			tree[tree_index].mx = max(tree[tree_index].mx, heigh);
		}
		else {
			tree[tree_index].mn = min(tree[tree_index].mn, heigh);
			tree[tree_index].mx = min(tree[tree_index].mx, heigh);
		}
		return;
	}
	lazy(tree_index);
	tree[tree_index].mn = 2000010;
	tree[tree_index].mx = 0;
	update(tree_index * 2, tl, (tl + tr) / 2, l, r, type, heigh);
	update(tree_index * 2 + 1, (tl + tr) / 2 + 1, tr, l, r, type, heigh);
}

void get(int l, int r, int tree_index) {
	if (l == r) {
		ans[l] = tree[tree_index].mn;
		return;
	}
	lazy(tree_index);
	get(l, (l + r) / 2, tree_index * 2);
	get((l + r) / 2 + 1, r, tree_index * 2 + 1);
}
#include "wall.h"
void buildWall(int n, int k, int* op, int* left, int* right, int* height, int* finalheight) {
	for (int i = 0; i < k; i++) {
		update(1, 0, n - 1, left[i], right[i], op[i], height[i]);
	}
	get(0, n - 1, 1);
	for (int i = 0; i < n; i++) {
		finalheight[i] = ans[i];
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8020 KB Output is correct
2 Correct 4 ms 8148 KB Output is correct
3 Correct 4 ms 8148 KB Output is correct
4 Correct 9 ms 8652 KB Output is correct
5 Correct 8 ms 8548 KB Output is correct
6 Correct 8 ms 8660 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8020 KB Output is correct
2 Correct 129 ms 15856 KB Output is correct
3 Correct 149 ms 12008 KB Output is correct
4 Correct 394 ms 28140 KB Output is correct
5 Correct 307 ms 29196 KB Output is correct
6 Correct 260 ms 27608 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8020 KB Output is correct
2 Correct 5 ms 8148 KB Output is correct
3 Correct 5 ms 8148 KB Output is correct
4 Correct 9 ms 8660 KB Output is correct
5 Correct 8 ms 8652 KB Output is correct
6 Correct 7 ms 8548 KB Output is correct
7 Correct 4 ms 8072 KB Output is correct
8 Correct 140 ms 21764 KB Output is correct
9 Correct 145 ms 15692 KB Output is correct
10 Correct 385 ms 28148 KB Output is correct
11 Correct 292 ms 29300 KB Output is correct
12 Correct 268 ms 27584 KB Output is correct
13 Correct 5 ms 8120 KB Output is correct
14 Correct 158 ms 21776 KB Output is correct
15 Correct 27 ms 9836 KB Output is correct
16 Correct 380 ms 28452 KB Output is correct
17 Correct 260 ms 27820 KB Output is correct
18 Correct 279 ms 27844 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8148 KB Output is correct
2 Correct 4 ms 8148 KB Output is correct
3 Correct 4 ms 8148 KB Output is correct
4 Correct 8 ms 8660 KB Output is correct
5 Correct 10 ms 8624 KB Output is correct
6 Correct 8 ms 8660 KB Output is correct
7 Correct 4 ms 8148 KB Output is correct
8 Correct 138 ms 21708 KB Output is correct
9 Correct 157 ms 15728 KB Output is correct
10 Correct 416 ms 28136 KB Output is correct
11 Correct 280 ms 29308 KB Output is correct
12 Correct 260 ms 27636 KB Output is correct
13 Correct 5 ms 8148 KB Output is correct
14 Correct 144 ms 21760 KB Output is correct
15 Correct 26 ms 9860 KB Output is correct
16 Correct 364 ms 28396 KB Output is correct
17 Correct 259 ms 27820 KB Output is correct
18 Correct 266 ms 27836 KB Output is correct
19 Correct 624 ms 77344 KB Output is correct
20 Correct 610 ms 74760 KB Output is correct
21 Correct 650 ms 77344 KB Output is correct
22 Correct 677 ms 74764 KB Output is correct
23 Correct 635 ms 74768 KB Output is correct
24 Correct 646 ms 74828 KB Output is correct
25 Correct 604 ms 74816 KB Output is correct
26 Correct 597 ms 77324 KB Output is correct
27 Correct 586 ms 77276 KB Output is correct
28 Correct 607 ms 74848 KB Output is correct
29 Correct 647 ms 74772 KB Output is correct
30 Correct 632 ms 74824 KB Output is correct