oj.uz

Submission #794363

# Submission time Handle Problem Language Result Execution time Memory
794363 2023-07-26T13:26:54 Z AkramElOmrani Wall (IOI14_wall) C++17
100 / 100
 485 ms 99312 KB 
#pragma once

#include <bits/stdc++.h>
using namespace std;

template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
 
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__);

struct Node {
	int mn = 1e9, mx = 0;
};
vector<Node> tree;

void upd(int node, int l, int r, int low, int high, int op, int v) {
	v = max(v, tree[node].mx);
	v = min(v, tree[node].mn);
	if(r < low || high < l) return;
	if(low <= l && r <= high) {
		if(op == 1) {
			// dbg(v)
			tree[node].mx = v;
		} else if(op == 2) {
			tree[node].mn = v;
		} else assert(false);
		return;
	}
	int mid = (l + r) / 2;
	upd(node * 2, l, mid, low, high, op, v);
	upd(node * 2 + 1, mid + 1, r, low, high, op, v);
}


void build(int node, int l, int r, int finalHeight[], int ans) {
	ans = max(ans, tree[node].mx);
	ans = min(ans, tree[node].mn);
	if(l == r) {
		finalHeight[l] = ans;
		return;
	}
	int mid = (l + r) / 2;
	build(node * 2, l, mid, finalHeight, ans);
	build(node * 2 + 1, mid + 1, r, finalHeight, ans);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
	tree.resize(n * 4);

	for(int i = k - 1; i >= 0; --i) {
		upd(1, 0, n - 1, left[i], right[i], op[i], height[i]);
	}

	build(1, 0, n - 1, finalHeight, 0);
}

Compilation message

wall.cpp:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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 4 ms 884 KB Output is correct
5 Correct 3 ms 852 KB Output is correct
6 Correct 3 ms 836 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 110 ms 13824 KB Output is correct
3 Correct 99 ms 7920 KB Output is correct
4 Correct 266 ms 21388 KB Output is correct
5 Correct 187 ms 22384 KB Output is correct
6 Correct 201 ms 20880 KB Output is correct

Subtask #3
29.0 / 29.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 1 ms 340 KB Output is correct
4 Correct 4 ms 820 KB Output is correct
5 Correct 3 ms 852 KB Output is correct
6 Correct 4 ms 852 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 108 ms 13836 KB Output is correct
9 Correct 101 ms 7952 KB Output is correct
10 Correct 282 ms 21388 KB Output is correct
11 Correct 193 ms 22440 KB Output is correct
12 Correct 184 ms 20864 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 123 ms 13844 KB Output is correct
15 Correct 16 ms 2008 KB Output is correct
16 Correct 263 ms 21636 KB Output is correct
17 Correct 197 ms 21128 KB Output is correct
18 Correct 210 ms 21108 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 360 KB Output is correct
4 Correct 4 ms 820 KB Output is correct
5 Correct 3 ms 852 KB Output is correct
6 Correct 3 ms 852 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 109 ms 13888 KB Output is correct
9 Correct 101 ms 7952 KB Output is correct
10 Correct 260 ms 21456 KB Output is correct
11 Correct 186 ms 22480 KB Output is correct
12 Correct 186 ms 21088 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 111 ms 13820 KB Output is correct
15 Correct 16 ms 2040 KB Output is correct
16 Correct 281 ms 21632 KB Output is correct
17 Correct 201 ms 21060 KB Output is correct
18 Correct 186 ms 21120 KB Output is correct
19 Correct 484 ms 99232 KB Output is correct
20 Correct 450 ms 96760 KB Output is correct
21 Correct 471 ms 99276 KB Output is correct
22 Correct 485 ms 96820 KB Output is correct
23 Correct 440 ms 96792 KB Output is correct
24 Correct 435 ms 96760 KB Output is correct
25 Correct 468 ms 96748 KB Output is correct
26 Correct 449 ms 99224 KB Output is correct
27 Correct 438 ms 99312 KB Output is correct
28 Correct 425 ms 96684 KB Output is correct
29 Correct 438 ms 96700 KB Output is correct
30 Correct 446 ms 96736 KB Output is correct