Submission #776200

#	Time	Username	Problem	Language	Result	Execution time	Memory
776200		SanguineChameleon	Radio Towers (IOI22_towers)	C++17	100 / 100	1471 ms	126592 KiB

towers

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

struct node1 {
	pair<int, int> max_val, min_val;
	int max_diff, min_diff;

	node1(): max_val(make_pair(0, 0)), min_val(make_pair(0, 0)), max_diff(0), min_diff(0) {};

	node1(pair<int, int> _max_val, pair<int, int> _min_val, int _max_diff, int _min_diff): max_val(_max_val), min_val(_min_val), max_diff(_max_diff), min_diff(_min_diff) {};
};

struct node2 {
	int cnt, min_pos, max_pos;
	node2 *left;
	node2 *right;

	node2(): cnt(0), min_pos(0), max_pos(0), left(nullptr), right(nullptr) {};

	node2(int _cnt, int _min_pos, int _max_pos, node2 *_left, node2 *_right): cnt(_cnt), min_pos(_min_pos), max_pos(_max_pos), left(_left), right(_right) {};
};

const int inf = 1e9 + 20;
const int maxN = 1e5 + 20;
int H[maxN];
node1 tree1[maxN * 4];
int N;

node1 merge1(node1 left, node1 right) {
	return node1(max(left.max_val, right.max_val), min(left.min_val, right.min_val), max(max(left.max_diff, right.max_diff), left.max_val.first - right.min_val.first), min(min(left.min_diff, right.min_diff), left.min_val.first - right.max_val.first));
}

node2* merge2(node2 *left, node2 *right) {
	return new node2(left->cnt + right->cnt, min(left->min_pos, right->min_pos), max(left->max_pos, right->max_pos), left, right);
}

void build1(int id, int lt, int rt) {
	if (lt == rt) {
		tree1[id] = node1(make_pair(H[lt], lt), make_pair(H[lt], lt), 0, 0);
		return;
	}
	int mt = (lt + rt) / 2;
	build1(id * 2, lt, mt);
	build1(id * 2 + 1, mt + 1, rt);
	tree1[id] = merge1(tree1[id * 2], tree1[id * 2 + 1]);
}

node2* build2(int lt, int rt) {
	if (lt == rt) {
		return new node2(0, N + 1, 0, nullptr, nullptr);
	}
	int mt = (lt + rt) / 2;
	return new node2(0, N + 1, 0, build2(lt, mt), build2(mt + 1, rt));
}

node2* update2(node2 *cur, int lt, int rt, int pos) {
	if (lt == rt) {
		return new node2(1, pos, pos, nullptr, nullptr);
	}
	int mt = (lt + rt) / 2;
	if (pos <= mt) {
		return merge2(update2(cur->left, lt, mt, pos), cur->right);
	}
	else {
		return merge2(cur->left, update2(cur->right, mt + 1, rt, pos));
	}
}

node2* get2(node2 *cur, int lt, int rt, int ql, int qr) {
	if (lt == ql && rt == qr) {
		return cur;
	}
	int mt = (lt + rt) / 2;
	if (qr <= mt) {
		return get2(cur->left, lt, mt, ql, qr);
	}
	else if (ql >= mt + 1) {
		return get2(cur->right, mt + 1, rt, ql, qr);
	}
	else {
		return merge2(get2(cur->left, lt, mt, ql, mt), get2(cur->right, mt + 1, rt, mt + 1, qr));
	}
}

int _get_firstL(int id, int lt, int rt, int pos, int low) {
	if (lt == rt) {
		return lt - (H[lt] < low);
	}
	if (tree1[id].max_val.first < low) {
		return lt - 1;
	}
	int mt = (lt + rt) / 2;
	if (pos <= mt) {
		return _get_firstL(id * 2, lt, mt, pos, low);
	}
	else {
		int res = _get_firstL(id * 2 + 1, mt + 1, rt, pos, low);
		return (res >= mt + 1 ? res : _get_firstL(id * 2, lt, mt, pos, low));
	}
}

int _get_firstR(int id, int lt, int rt, int pos, int low) {
	if (lt == rt) {
		return rt + (H[rt] < low);
	}
	if (tree1[id].max_val.first < low) {
		return rt + 1;
	}
	int mt = (lt + rt) / 2;
	if (pos >= mt + 1) {
		return _get_firstR(id * 2 + 1, mt + 1, rt, pos, low);
	}
	else {
		int res = _get_firstR(id * 2, lt, mt, pos, low);
		return (res <= mt ? res : _get_firstR(id * 2 + 1, mt + 1, rt, pos, low));
	}
}

node1 get1(int id, int lt, int rt, int ql, int qr) {
	if (lt == ql && rt == qr) {
		return tree1[id];
	}
	int mt = (lt + rt) / 2;
	if (qr <= mt) {
		return get1(id * 2, lt, mt, ql, qr);
	}
	else if (ql >= mt + 1) {
		return get1(id * 2 + 1, mt + 1, rt, ql, qr);
	}
	else {
		return merge1(get1(id * 2, lt, mt, ql, mt), get1(id * 2 + 1, mt + 1, rt, mt + 1, qr));
	}
}

int get_firstL(int pos, int D) {
	return _get_firstL(1, 1, N, pos, H[pos] + D);
}

int get_firstR(int pos, int D) {
	return _get_firstR(1, 1, N, pos, H[pos] + D);
}

bool checkL(int pos, int D, int L) {
	int firstL = get_firstL(pos, D);
	if (firstL <= L) {
		return false;
	}
	auto left = get1(1, 1, N, L, firstL - 1);
	auto right = get1(1, 1, N, firstL, pos);
	return (left.min_diff <= -D) || (right.max_val.first - left.min_val.first >= D);
}

bool checkR(int pos, int D, int R) {
	int firstR = get_firstR(pos, D);
	if (firstR >= R) {
		return false;
	}
	auto right = get1(1, 1, N, firstR + 1, R);
	auto left = get1(1, 1, N, pos, firstR);
	return (right.max_diff >= D) || (left.max_val.first - right.min_val.first >= D);
}

vector<int> dists;
vector<int> add;
vector<node2*> roots;

void init(int _N, vector<int> _H) {
	if (_N <= 2) {
		return;
	}
	N = _N;
	for (int i = 1; i <= N; i++) {
		H[i] = _H[i - 1];
	}
	build1(1, 1, N);
	vector<int> extr;
	if (H[1] < H[2]) {
		extr.push_back(1);
	}
	for (int i = 2; i <= N - 1; i++) {
		if ((H[i - 1] < H[i]) ^ (H[i] < H[i + 1])) {
			extr.push_back(i);
		}
	}
	if (H[N - 1] > H[N]) {
		extr.push_back(N);
	}
	set<int> S(extr.begin(), extr.end());
	priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> Q;
	for (int i = 1; i < (int)extr.size(); i++) {
		Q.emplace(abs(H[extr[i - 1]] - H[extr[i]]), make_pair(extr[i - 1], extr[i]));
	}
	while (!Q.empty()) {
		int dist = Q.top().first;
		int X = Q.top().second.first;
		int Y = Q.top().second.second;
		Q.pop();
		auto it = S.find(X);
		if (it == S.end() || next(it) == S.end() || *next(it) != Y) {
			continue;
		}
		dists.push_back(dist);
		add.push_back(H[X] < H[Y] ? X : Y);
		it = S.erase(it);
		it = S.erase(it);
		if (it != S.begin() && it != S.end()) {
			int prv = *prev(it);
			int nxt = *it;
			Q.emplace(abs(H[prv] - H[nxt]), make_pair(prv, nxt));
		}
	}
	dists.push_back(inf);
	add.push_back(*S.begin());
	roots.resize((int)dists.size() + 1);
	roots.back() = build2(1, N);
	for (int i = (int)roots.size() - 2; i >= 0; i--) {
		roots[i] = update2(roots[i + 1], 1, N, add[i]);
	}
}

int max_towers(int L, int R, int D) {
	L++;
	R++;
	if (R - L <= 1) {
		return 1;
	}
	node2 *range = get2(roots[lower_bound(dists.begin(), dists.end(), D) - dists.begin()], 1, N, L, R);
	if (!range->cnt) {
		int pos = get1(1, 1, N, L, R).min_val.second;
		return 1 + (checkL(pos, D, L) || checkR(pos, D, R));
	}
	else {
		return range->cnt + checkL(range->min_pos, D, L) + checkR(range->max_pos, D, R);
	}
}

• 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