Submission #833192

#	Time	Username	Problem	Language	Result	Execution time	Memory
833192		pavement	Radio Towers (IOI22_towers)	C++17	23 / 100	4099 ms	4108 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 <= V[i] - D) {
					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 <= V[i] - D) {
					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);
	}
	vector<ii> segs;
	for (int i = 0; i < (int)V.size(); i++) {
		if (cl[i] != -1 && cr[i] != (int)V.size()) {
			segs.eb(cr[i], cl[i]);
		}
	}
	sort(segs.begin(), segs.end());
	int ans = 0, max_r = -1;
	for (auto [r, l] : segs) {
		if (l >= max_r) {
			ans++;
			max_r = r;
		}
	}
	return ans + 1;
}

• 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