oj.uz

Submission #817753

# Submission time Handle Problem Language Result Execution time Memory
817753 2023-08-09T15:40:25 Z Temmie Radio Towers (IOI22_towers) C++17
0 / 100
 1467 ms 304676 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, mn_ind = -1;
		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 }),
				l.mn < r.mn ? l.mn_ind : r.mn_ind
			};
		}
	};
	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], bin[0][i].mn_ind = -1;
		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 (!pit.sum) {
		pit.sum++;
		pit.mn = pit.mx = sparse.query(L, R + 1).mn_ind;
	}
	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 720 ms 175948 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 7 ms 5200 KB Output is correct
3 Correct 7 ms 5200 KB Output is correct
4 Correct 7 ms 5200 KB Output is correct
5 Correct 7 ms 5200 KB Output is correct
6 Correct 7 ms 5200 KB Output is correct
7 Correct 7 ms 5200 KB Output is correct
8 Correct 6 ms 5200 KB Output is correct
9 Correct 6 ms 5200 KB Output is correct
10 Correct 6 ms 5200 KB Output is correct
11 Correct 6 ms 5200 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 7 ms 5200 KB Output is correct
3 Correct 7 ms 5200 KB Output is correct
4 Correct 7 ms 5200 KB Output is correct
5 Correct 7 ms 5200 KB Output is correct
6 Correct 7 ms 5200 KB Output is correct
7 Correct 7 ms 5200 KB Output is correct
8 Correct 6 ms 5200 KB Output is correct
9 Correct 6 ms 5200 KB Output is correct
10 Correct 6 ms 5200 KB Output is correct
11 Correct 6 ms 5200 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 1044 ms 301532 KB Output is correct
2 Correct 1343 ms 303772 KB Output is correct
3 Correct 1351 ms 303872 KB Output is correct
4 Correct 1356 ms 304624 KB Output is correct
5 Correct 1467 ms 304636 KB Output is correct
6 Correct 1339 ms 304612 KB Output is correct
7 Correct 1400 ms 304676 KB Output is correct
8 Correct 1252 ms 302292 KB Output is correct
9 Correct 1322 ms 302304 KB Output is correct
10 Correct 1155 ms 302240 KB Output is correct
11 Correct 1153 ms 302260 KB Output is correct
12 Incorrect 1286 ms 302236 KB 170th lines differ - on the 1st token, expected: '2', found: '1'
13 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 397 ms 68188 KB Output is correct
2 Incorrect 1358 ms 303880 KB 13344th lines differ - on the 1st token, expected: '1', found: '0'
3 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1232 KB Output is correct
2 Correct 7 ms 5200 KB Output is correct
3 Correct 7 ms 5200 KB Output is correct
4 Correct 7 ms 5200 KB Output is correct
5 Correct 7 ms 5200 KB Output is correct
6 Correct 7 ms 5200 KB Output is correct
7 Correct 7 ms 5200 KB Output is correct
8 Correct 6 ms 5200 KB Output is correct
9 Correct 6 ms 5200 KB Output is correct
10 Correct 6 ms 5200 KB Output is correct
11 Correct 6 ms 5200 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 720 ms 175948 KB 12th lines differ - on the 1st token, expected: '2', found: '1'
2 Halted 0 ms 0 KB -