Submission #987812

#	Time	Username	Problem	Language	Result	Execution time	Memory
987812		siewjh	Radio Towers (IOI22_towers)	C++17	100 / 100	1562 ms	124604 KiB

towers

#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
struct node{
	int s, m, e, val;
	node *l, *r;
	node(int _s, int _e, vector<int> &arr){
		s = _s, e = _e, m = (s + e) >> 1;
		if (s == e) val = arr[s];
		else{
			l = new node(s, m, arr); r = new node(m + 1, e, arr);
			val = max(l->val, r->val);
		}
	}
	int query(int x, int y){
		if (x > y) return -1;
		if (x == s && y == e) return val;
		else if (y <= m) return l->query(x, y);
		else if (x > m) return r->query(x, y);
		else return max(l->query(x, m), r->query(m + 1, y));
	}
};
struct node2{
	int s, m, e, val;
	node2 *l = nullptr, *r = nullptr;
	node2 (int _s, int _e){
		s = _s, e = _e, m = (s + e) >> 1, val = 0;
		if (s != e){
			l = new node2(s, m); r = new node2(m + 1, e);
		}
	}
	node2 (node2 *x){
		s = x->s, e = x->e, m = x->m, val = x->val;
		l = x->l; r = x->r;
	}
	void update(int p, int v){
		val += v;
		if (s == e) return;
		else if (p <= m){
			l = new node2(l); l->update(p, v);
		}
		else{
			r = new node2(r); r->update(p, v);
		}
	}
	int cnt(int x, int y){
		if (x == s && y == e) return val;
		else if (y <= m) return l->cnt(x, y);
		else if (x > m) return r->cnt(x, y);
		else return l->cnt(x, m) + r->cnt(m + 1, y);
	}
	int lf(int x, int y){
		if (val == 0) return -1;
		if (s == e) return s;
		else if (y <= m) return l->lf(x, y);
		else if (x > m) return r->lf(x, y);
		else{
			int v = l->lf(x, m);
			return (v != -1 ? v : r->lf(m + 1, y));
		}
	}
	int rf(int x, int y){
		if (val == 0) return -1;
		if (s == e) return s;
		else if (y <= m) return l->rf(x, y);
		else if (x > m) return r->rf(x, y);
		else{
			int v = r->rf(m + 1, y);
			return (v != -1 ? v : l->rf(x, m));
		}
	}
};
node *lst, *rst;
node2 *proots[MAXN];
vector<int> disc; int dsz;
void init(int N, vector<int> H){
	node *root = new node(0, N - 1, H);
	vector<int> ld(N), rd(N), fd(N);
	vector<int> st; st.push_back(-1);
	for (int i = 0; i < N; i++){
		while (st.back() != -1 && H[st.back()] > H[i]) st.pop_back();
		ld[i] = max(0, root->query(st.back() + 1, i - 1) - H[i]);
		st.push_back(i);
	}
	st.clear(); st.push_back(N);
	for (int i = N - 1; i >= 0; i--){
		while (st.back() != N && H[st.back()] > H[i]) st.pop_back();
		rd[i] = max(0, root->query(i + 1, st.back() - 1) - H[i]);
		st.push_back(i);
	}
	lst = new node(0, N - 1, ld); rst = new node(0, N - 1, rd);
	for (int i = 0; i < N; i++){
		fd[i] = min(ld[i], rd[i]);
		disc.push_back(fd[i]);
	}
	sort(disc.begin(), disc.end());
	disc.resize(distance(disc.begin(), unique(disc.begin(), disc.end())));
	dsz = disc.size();
	vector<vector<int>> ord(dsz + 1);
	for (int i = 0; i < N; i++){
		int id = lower_bound(disc.begin(), disc.end(), fd[i]) - disc.begin();
		ord[dsz - id].push_back(i);
	}
	proots[0] = new node2(0, N - 1);
	for (int i = 1; i <= dsz; i++){
		proots[i] = new node2(proots[i - 1]);
		for (int x : ord[i]) proots[i]->update(x, 1);
	}
}
int max_towers(int L, int R, int D){
	int id = dsz - (lower_bound(disc.begin(), disc.end(), D) - disc.begin());
	int ans = proots[id]->cnt(L, R);
	int lb = (ans == 0 ? R + 1 : proots[id]->lf(L, R)), rb = (ans == 0 ? L - 1 : proots[id]->rf(L, R));
	if (rst->query(L, lb - 1) >= D) ans++;
	if (lst->query(rb + 1, R) >= D) ans++;
	return max(ans, 1);
}

• 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