제출 #1039852

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1039852		42kangaroo	Radio Towers (IOI22_towers)	C++17	17 / 100	1168 ms	49372 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;
};

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;
		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++;
			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});
		return a.size() - 1;
	}

	int get(int i, int lq, int rq) {
		if (a[i].riR <= lq || rq <= a[i].leR) return 0;
		if (lq <= a[i].leR && a[i].riR <= rq) return a[i].su;
		return get(a[i].l, lq, rq) + get(a[i].r, lq, rq);
	}
};

SegTePer perSe;
vector<pair<int,int>> whi;

void init(int N, std::vector<int> H) {
	SegTeMa maSe{vector<int>(4*N)};
	SegTeRan raSe{vector<int>(4*N, 0)};
	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;
	return perSe.get(to, L, R + 1);
}

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