Submission #1040883

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040883		42kangaroo	Radio Towers (IOI22_towers)	C++17	100 / 100	1440 ms	72512 KiB

towers

#include "towers.h"
#include "bits/stdc++.h"

using namespace std;

struct SegTeRan {
	vector<int> a;

	int get(int l, int r, int i, int lq, int rq) {
		if (r <= lq || rq <= l) return 0;
		if (lq <= l && r <= rq) return a[i];
		int m = (l + r)/2;
		return max(get(l, m, 2*i + 1, lq, rq), get(m, r, 2*i + 2, lq, rq));
	}

	int set(int l, int r, int i, int k, int v) {
		if (k < l || r <= k) return a[i];
		if (l + 1 == r) return a[i] = v;
		int m = (l + r)/2;
		return a[i] = max(set(l, m, 2*i + 1, k, v), set(m, r, 2*i + 2, k, v));
	}
};


struct SegTeMa{
	vector<int> a;

	int build(int l, int r, int i, vector<int>& in) {
		if (l + 1 == r) return a[i] = in[l];
		int m = (l + r)/2;
		return a[i] = max(build(l, m, 2*i + 1, in), build(m, r, 2*i + 2, in));
	}

	int firLe(int l, int r, int i, int k, int hi) {
		if (l > k) return -1;
		if (a[i] < hi) return -1;
		if (l + 1 == r) return l;
		int m = (l + r)/2;
		int reR = firLe(m, r, 2*i + 2, k, hi);
		if (reR != -1) return reR;
		return firLe(l, m, 2*i + 1, k, hi);
	}

	int firRi(int l, int r, int i, int k, int hi) {
		if (r <= k) return -1;
		if (a[i] < hi) return -1;
		if (l + 1 == r) return l;
		int m = (l + r)/2;
		int reR = firRi(l, m, 2*i + 1, k, hi);
		if (reR != -1) return reR;
		return firRi(m, r, 2*i + 2, k, hi);
	}
};

struct Node {
	int l, r, leR, riR, su, mi, ma;
};

tuple<int,int,int> comb(tuple<int,int,int> l, tuple<int,int,int> r) {
	return {get<0>(l) + get<0>(r), min(get<1>(l), get<1>(r)), max(get<2>(l), get<2>(r))};
}

struct SegTePer{
	vector<Node> a;

	void build(int i, int l, int r) {
		a[i].leR = l; a[i].riR = r; a[i].su = 0;
		a[i].mi = 1e9; a[i].ma = -1;
		if (l + 1 == r) return;
		int m = (l + r)/2;
		a[i].l = a.size();
		a.push_back({});
		build(a[i].l, l, m);
		a[i].r = a.size();
		a.push_back({});
		build(a[i].r, m, r);
	}

	int inc(int i, int k) {
		if (a[i].leR > k || a[i].riR <= k) return i;
		if (a[i].leR + 1 == a[i].riR) {
			a.push_back(a[i]);
			a.back().su++;
			a.back().mi = a.back().ma = a[i].leR;
			return a.size() - 1;
		}
		int le = inc(a[i].l, k), ri = inc(a[i].r, k);
		a.push_back({le, ri, a[i].leR, a[i].riR, a[le].su + a[ri].su, min(a[le].mi, a[ri].mi), max(a[le].ma, a[ri].ma)});
		return a.size() - 1;
	}

	tuple<int,int,int> get(int i, int lq, int rq) {
		if (a[i].riR <= lq || rq <= a[i].leR) return {0, 1e9, -1};
		if (lq <= a[i].leR && a[i].riR <= rq) return {a[i].su, a[i].mi, a[i].ma};
		return comb(get(a[i].l, lq, rq), get(a[i].r, lq, rq));
	}
};


struct DifStr{
	int mi, ma, leD, riD;
};

DifStr comb(DifStr l, DifStr r) {
	return {min(l.mi, r.mi), max(l.ma, r.ma), max(l.leD, max(r.leD, r.ma - l.mi)), max(l.riD, max(r.riD, l.ma - r.mi))};
}

struct SegTeDif {
	vector<DifStr> a;

	DifStr build(int l, int r, int i, vector<int> &in) {
		if (l + 1 == r) return a[i] = {in[l], in[l], 0, 0};
		int m = (l + r) / 2;
		return a[i] = comb(build(l, m, 2 * i + 1, in), build(m, r, 2 * i + 2, in));
	}

	DifStr get(int l, int r, int i, int lq, int rq) {
		if (rq <= l || r <= lq) return {(int)1e9, -1, 0, 0};
		if (lq <= l && r <= rq) return a[i];
		int m = (l + r)/2;
		return comb(get(l, m, 2*i + 1, lq, rq), get(m, r, 2*i + 2, lq,rq));
	}
};

SegTePer perSe;
vector<pair<int,int>> whi;
SegTeMa maSe;
SegTeDif diSe;
int n;
vector<int> h;

void init(int N, std::vector<int> H) {
	n = N;
	h = H;
	maSe = SegTeMa{vector<int>(4*N)};
	SegTeRan raSe{vector<int>(4*N, 0)};
	diSe = SegTeDif{vector<DifStr>(4*N)};
	diSe.build(0, N, 0, H);
	maSe.build(0, N, 0, H);
	vector<int> o(N);
	std::iota(o.begin(), o.end(),0);
	std::sort(o.begin(), o.end(), [&](int l, int r){return H[l] < H[r];});
	vector<pair<int,int>> ch;
	for (int i = 0; i < N; ++i) {
		int l = 0, r = 1e9 + 1;
		while (l + 1 < r) {
			int m = l + (r  - l)/2;
			int leB = maSe.firLe(0, N, 0, o[i], H[o[i]] + m), reB = maSe.firRi(0, N, 0, o[i], H[o[i]] + m);
			if (leB == -1) leB = 0;
			if (reB == -1) reB = N;
			if (raSe.get(0, N, 0, leB, reB) < m) l = m;
			else r = m;
		}
		raSe.set(0, N, 0, o[i], l);
		ch.push_back({l, o[i]});
	}
	std::sort(ch.begin(), ch.end(), greater<>());
	perSe.a.push_back({});
	whi.push_back({1e9 + 1, 0});
	perSe.build(0, 0, N);
	for (int i = 0; i < N; ++i) {
		whi.push_back({ch[i].first, perSe.inc(whi.back().second, ch[i].second)});
	}
}


int max_towers(int L, int R, int D) {
	int to = std::lower_bound(whi.rbegin(), whi.rend(),make_pair(D, 0))->second;
	auto [su, mi, ma] = perSe.get(to, L, R + 1);
	if (su == 0) {
		su = 1;
		int l = L + 1, r = R + 2;
		while (l + 1 < r) {
			int m = (l + r)/2;
			if (diSe.get(0, n, 0, L, m).leD >= D) r = m;
			else l = m;
		}
		if (r <= R) {
			su += (diSe.get(0, n, 0, r - 1, R + 1).riD >= D);
		}
	} else {
		int lB = maSe.firLe(0, n, 0, mi, h[mi] + D), rB = maSe.firRi(0, n, 0, ma, h[ma] + D);
		if (lB > L) {
			su += (diSe.get(0, n, 0, L, lB+ 1).leD >= D);
		}
		if (rB != -1 && rB < R) {
			su += (diSe.get(0, n, 0, rB, R + 1).riD >= D);
		}
	}
	return su;
}

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