Submission #833236

#	Time	Username	Problem	Language	Result	Execution time	Memory
833236		pavement	Radio Towers (IOI22_towers)	C++17	56 / 100	967 ms	20624 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;
bool is_init;
vector<int> H, cl, cr;
vector<vector<int> > anc;
vector<ii> segs;

void init(int N, vector<int> H) {
	::N = N;
	::H = H;
	cl = vector<int>(N, -1);
	cr = vector<int>(N, N);
	anc = vector<vector<int> >(20, vector<int>(N, -1));
}

struct node {
	node *left, *right;
	int S, E;
	ii val;
	node(int _s, int _e) : S(_s), E(_e), val(-1, -1) {
		if (S == E) {
			return;
		}
		int M = (S + E) / 2;
		left = new node(S, M);
		right = new node(M + 1, E);
	}
	void upd(int p, ii v) {
		val = max(val, v);
		if (S == E) {
			return;
		}
		int M = (S + E) / 2;
		if (p <= M) {
			left->upd(p, v);
		} else {
			right->upd(p, v);
		}
	}
	ii qry(int r) {
		if (r < S) {
			return mp(-1, -1);
		}
		if (E <= r) {
			return val;
		}
		return max(left->qry(r), right->qry(r));
	}
} *root;

int max_towers(int L, int R, int D) {
	if (!is_init) {
		vector<ii> vec;
		for (int i = 0; i < N; i++) {
			{
				int lo = 0, hi = (int)vec.size() - 1;
				while (lo <= hi) {
					int mid = (lo + hi) / 2;
					if (vec[mid].first <= H[i] - D) {
						cl[i] = vec[mid].second;
						lo = mid + 1;
					} else {
						hi = mid - 1;
					}
				}
			}
			while (!vec.empty() && vec.back().first >= H[i]) {
				vec.pop_back();
			}
			vec.eb(H[i], i);
		}
		vec.clear();
		for (int i = N - 1; i >= 0; i--) {
			{
				int lo = 0, hi = (int)vec.size() - 1;
				while (lo <= hi) {
					int mid = (lo + hi) / 2;
					if (vec[mid].first <= H[i] - D) {
						cr[i] = vec[mid].second;
						lo = mid + 1;
					} else {
						hi = mid - 1;
					}
				}
			}
			while (!vec.empty() && vec.back().first >= H[i]) {
				vec.pop_back();
			}
			vec.eb(H[i], i);
		}
		for (int i = 0; i < N; i++) {
			if (cl[i] != -1 && cr[i] != N) {
				segs.eb(cr[i], cl[i]);
			}
		}
		sort(segs.begin(), segs.end());
		root = new node(0, N - 1);
		for (int i = 0; i < (int)segs.size(); i++) {
			int to = root->qry(segs[i].second).second;
			anc[0][i] = to;
			for (int k = 1; k < 20; k++) {
				if (anc[k - 1][i] == -1) {
					break;
				}
				anc[k][i] = anc[k - 1][anc[k - 1][i]];
			}
			root->upd(segs[i].first, mp(segs[i].second, i));
		}
		is_init = 1;
	}
	int st = root->qry(R).second;
	if (st == -1 || segs[st].second < L) {
		return 1;
	}
	int ans = 2;
	for (int k = 19; k >= 0; k--) {
		if (anc[k][st] != -1 && segs[anc[k][st]].second >= L) {
			st = anc[k][st];
			ans += (1 << k);
		}
	}
	return ans;
}

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