Submission #833179

#	Time	Username	Problem	Language	Result	Execution time	Memory
833179		pavement	Radio Towers (IOI22_towers)	C++17	23 / 100	4070 ms	3784 KiB

towers

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

#define eb emplace_back
#define mp make_pair

using ii = pair<int, int>;

int N;
vector<int> H;

void init(int N, vector<int> H) {
	::N = N;
	::H = H;
}

int max_towers(int L, int R, int D) {
	vector<int> V(H.begin() + L, H.begin() + R + 1), cl(V.size(), -1), cr(V.size(), V.size());
	vector<ii> vec;
	for (int i = 0; i < (int)V.size(); i++) {
		{
			int lo = 0, hi = (int)vec.size() - 1;
			while (lo <= hi) {
				int mid = (lo + hi) / 2;
				if (vec[mid].first - D >= V[i]) {
					cl[i] = vec[mid].second;
					lo = mid + 1;
				} else {
					hi = mid - 1;
				}
			}
		}
		while (!vec.empty() && vec.back().first <= V[i]) {
			vec.pop_back();
		}
		vec.eb(V[i], i);
	}
	vec.clear();
	for (int i = (int)V.size() - 1; i >= 0; i--) {
		{
			int lo = 0, hi = (int)vec.size() - 1;
			while (lo <= hi) {
				int mid = (lo + hi) / 2;
				if (vec[mid].first - D >= V[i]) {
					cr[i] = vec[mid].second;
					lo = mid + 1;
				} else {
					hi = mid - 1;
				}
			}
		}
		while (!vec.empty() && vec.back().first <= V[i]) {
			vec.pop_back();
		}
		vec.eb(V[i], i);
	}
	//~ for (int i : V) {
		//~ cout << i << ' ';
	//~ }
	//~ cout << '\n';
	//~ for (int i : cl) {
		//~ cout << i << ' ';
	//~ }
	//~ cout << '\n';
	//~ for (int i : cr) {
		//~ cout << i << ' ';
	//~ }
	//~ cout << '\n';
	function<int(int, int, bool, bool)> solve = [&](int l, int r, bool a, bool b) {
		if (l > r) {
			return 0;
		}
		ii to = mp((int)2e9, -1);
		for (int i = l; i <= r; i++) {
			if ((!a || l <= cl[i]) && (!b || cr[i] <= r)) {
				to = min(to, mp(V[i], i));
			}
		}
		if (to.second != -1) {
			return solve(l, to.second - 1, a, 1) + solve(to.second + 1, r, 1, b) + 1;
		} else {
			return 0;
		}
	};
	return solve(0, (int)V.size() - 1, 0, 0);
}

• Subtask 1: 0 / 4
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 17
• Subtask 6: 0 / 19
• Subtask 7: 0 / 23