oj.uz

Submission #817739

# Submission time Handle Problem Language Result Execution time Memory
817739 2023-08-09T15:26:57 Z Temmie Radio Towers (IOI22_towers) C++17
17 / 100
 1492 ms 298116 KB 
#include <bits/stdc++.h>

constexpr const int MXH = (int) 1e9 + 5;

struct Sparse {
	struct Item {
		int mn = MXH, mx = -MXH, anl = 0, anr = 0;
		static Item merge(const Item& l, const Item& r) {
			return {
				std::min(l.mn, r.mn), std::max(l.mx, r.mx),
				std::max({ l.anl, r.anl, r.mx - l.mn }), std::max({ l.anr, r.anr, l.mx - r.mx })
			};
		}
	};
	int size;
	std::vector <std::vector <Item>> bin;
	void init(const std::vector <int>& v) {
		bin.resize(17, std::vector <Item> (size = v.size()));
		for (int i = 0; i < size; i++) bin[0][i].mn = bin[0][i].mx = v[i];
		for (int b = 1; b < 17; b++)
			for (int i = 0; i + (1 << (b - 1)) < size; i++)
				bin[b][i] = Item::merge(bin[b - 1][i], bin[b - 1][i + (1 << (b - 1))]);
	}
	Item query(int l, int r) {
		Item res;
		if (l >= r || l < 0 || r >= size) return res;
		for (int b = 31 - __builtin_clz(r - l), range = r - l; ~b; l += ((range >> b) & 1) << b, b--)
			if (range & (1 << b))
				res = Item::merge(res, bin[b][l]);
		return res;
	}
};

struct PNode {
	struct Item {
		int sum = 0;
		int mn = MXH, mx = -MXH;
		static Item merge(const Item& l, const Item& r) {
			return { l.sum + r.sum, std::min(l.mn, r.mn), std::max(l.mx, r.mx) };
		}
	};
	typedef std::shared_ptr <PNode> PPNode;
	Item item;
	PPNode lc = nullptr, rc = nullptr;
	PNode(const Item& _item) : item(_item) { }
	PNode(PPNode _lc, PPNode _rc) : item(Item::merge(_lc->item, _rc->item)), lc(_lc), rc(_rc) { }
	static PPNode build(int l, int r) {
		if (!(r - l - 1)) return PPNode(new PNode({ }));
		int mid = (l + r) >> 1;
		return PPNode(new PNode(build(l, mid), build(mid, r)));
	}
	static PPNode set(PPNode node, int ind, int l, int r) {
		if (!(r - l - 1)) return PPNode(new PNode({ 1, ind, ind }));
		int mid = (l + r) >> 1;
		if (ind < mid) return PPNode(new PNode(set(node->lc, ind, l, mid), node->rc));
		return PPNode(new PNode(node->lc, set(node->rc, ind, mid, r)));
	}
	Item query(int tl, int tr, int l, int r) {
		if (l >= tr || r <= tl) return { };
		if (l >= tl && r <= tr) return item;
		int mid = (l + r) >> 1;
		return Item::merge(lc->query(tl, tr, l, mid), rc->query(tl, tr, mid, r));
	}
};

int n;
std::vector <int> h;
Sparse sparse;
std::vector <std::shared_ptr <PNode>> pst;
std::map <int, int> smp;

void init(int N, std::vector <int> H) {
	n = N + 4;
	h = H;
	h.insert(h.begin(), { 0, MXH });
	h.insert(h.end(), { MXH, 0 });
	sparse.init(h);
	std::vector <std::pair <int, int>> ord(N);
	for (int i = 2; i < n - 2; i++) ord[i - 2] = { h[i], i };
	std::sort(ord.begin(), ord.end());
	std::set <int> st = { 0, n - 1 };
	std::vector <int> tmon(n);
	for (auto [hei, i] : ord) {
		auto it = st.lower_bound(i);
		tmon[i] = std::max(0, std::min(sparse.query(*prev(it) + 1, i).mx, sparse.query(i + 1, *it).mx) - hei);
		st.insert(i);
	}
	smp[MXH] = 0;
	pst.push_back(PNode::build(0, 4 * n));
	for (int i = 2; i < n - 2; i++) ord[i - 2] = { tmon[i], i };
	std::sort(ord.rbegin(), ord.rend());
	for (auto [dv, i] : ord) {
		pst.push_back(PNode::set(pst.back(), i, 0, 4 * n));
		smp[dv] = (int) pst.size() - 1;
	}
}

int max_towers(int L, int R, int D) {
	L += 2, R += 2;
	std::shared_ptr <PNode> node = pst[smp.lower_bound(D)->second];
	PNode::Item pit = node->query(L, R + 1, 0, 4 * n);
	int ans = pit.sum;
	if (!ans) return 1;
	ans += sparse.query(L, pit.mn).anl >= D;
	ans += sparse.query(pit.mx + 1, R + 1).anr >= D;
	return ans;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 582 ms 171960 KB 12th lines differ - on the 1st token, expected: '2', found: '1'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1232 KB Output is correct
2 Correct 6 ms 5072 KB Output is correct
3 Correct 6 ms 5152 KB Output is correct
4 Correct 7 ms 5180 KB Output is correct
5 Correct 7 ms 5072 KB Output is correct
6 Correct 6 ms 5072 KB Output is correct
7 Correct 6 ms 5072 KB Output is correct
8 Correct 6 ms 5072 KB Output is correct
9 Correct 6 ms 5072 KB Output is correct
10 Correct 6 ms 5072 KB Output is correct
11 Correct 6 ms 5072 KB Output is correct
12 Incorrect 0 ms 208 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
13 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1232 KB Output is correct
2 Correct 6 ms 5072 KB Output is correct
3 Correct 6 ms 5152 KB Output is correct
4 Correct 7 ms 5180 KB Output is correct
5 Correct 7 ms 5072 KB Output is correct
6 Correct 6 ms 5072 KB Output is correct
7 Correct 6 ms 5072 KB Output is correct
8 Correct 6 ms 5072 KB Output is correct
9 Correct 6 ms 5072 KB Output is correct
10 Correct 6 ms 5072 KB Output is correct
11 Correct 6 ms 5072 KB Output is correct
12 Incorrect 0 ms 208 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
13 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1121 ms 295028 KB Output is correct
2 Correct 1374 ms 297272 KB Output is correct
3 Correct 1376 ms 297192 KB Output is correct
4 Correct 1338 ms 297996 KB Output is correct
5 Correct 1424 ms 297968 KB Output is correct
6 Correct 1332 ms 297972 KB Output is correct
7 Correct 1387 ms 297872 KB Output is correct
8 Correct 1072 ms 295708 KB Output is correct
9 Correct 1207 ms 295648 KB Output is correct
10 Correct 1235 ms 295572 KB Output is correct
11 Correct 1273 ms 295636 KB Output is correct
12 Incorrect 1069 ms 295576 KB 170th lines differ - on the 1st token, expected: '2', found: '1'
13 Halted 0 ms 0 KB -

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 320 ms 66624 KB Output is correct
2 Correct 1492 ms 297228 KB Output is correct
3 Correct 1437 ms 297156 KB Output is correct
4 Correct 1363 ms 297980 KB Output is correct
5 Correct 1294 ms 297992 KB Output is correct
6 Correct 1470 ms 298040 KB Output is correct
7 Correct 1414 ms 297916 KB Output is correct
8 Correct 1043 ms 295528 KB Output is correct
9 Correct 1079 ms 295644 KB Output is correct
10 Correct 1089 ms 295640 KB Output is correct
11 Correct 1057 ms 295540 KB Output is correct
12 Correct 488 ms 297208 KB Output is correct
13 Correct 553 ms 297968 KB Output is correct
14 Correct 520 ms 298116 KB Output is correct
15 Correct 390 ms 295640 KB Output is correct
16 Correct 393 ms 295576 KB Output is correct
17 Correct 483 ms 286656 KB Output is correct
18 Correct 491 ms 297208 KB Output is correct
19 Correct 494 ms 297112 KB Output is correct
20 Correct 527 ms 297888 KB Output is correct
21 Correct 653 ms 297968 KB Output is correct
22 Correct 516 ms 297968 KB Output is correct
23 Correct 530 ms 298008 KB Output is correct
24 Correct 392 ms 295576 KB Output is correct
25 Correct 417 ms 295600 KB Output is correct
26 Correct 445 ms 295632 KB Output is correct
27 Correct 398 ms 295608 KB Output is correct
28 Correct 7 ms 5072 KB Output is correct
29 Correct 7 ms 5164 KB Output is correct
30 Correct 7 ms 5112 KB Output is correct
31 Correct 6 ms 5080 KB Output is correct
32 Correct 7 ms 5072 KB Output is correct
33 Correct 3 ms 2384 KB Output is correct
34 Correct 8 ms 5292 KB Output is correct
35 Correct 7 ms 5164 KB Output is correct
36 Correct 7 ms 5188 KB Output is correct
37 Correct 8 ms 5072 KB Output is correct
38 Correct 9 ms 5072 KB Output is correct
39 Correct 6 ms 5188 KB Output is correct
40 Correct 9 ms 5088 KB Output is correct
41 Correct 6 ms 5072 KB Output is correct
42 Correct 8 ms 5132 KB Output is correct
43 Correct 8 ms 5072 KB Output is correct

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1232 KB Output is correct
2 Correct 6 ms 5072 KB Output is correct
3 Correct 6 ms 5152 KB Output is correct
4 Correct 7 ms 5180 KB Output is correct
5 Correct 7 ms 5072 KB Output is correct
6 Correct 6 ms 5072 KB Output is correct
7 Correct 6 ms 5072 KB Output is correct
8 Correct 6 ms 5072 KB Output is correct
9 Correct 6 ms 5072 KB Output is correct
10 Correct 6 ms 5072 KB Output is correct
11 Correct 6 ms 5072 KB Output is correct
12 Incorrect 0 ms 208 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
13 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 582 ms 171960 KB 12th lines differ - on the 1st token, expected: '2', found: '1'
2 Halted 0 ms 0 KB -