Submission #832440

#	Time	Username	Problem	Language	Result	Execution time	Memory
832440		ymm	Radio Towers (IOI22_towers)	C++17	100 / 100	1098 ms	49384 KiB

towers

#include "towers.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= l; --x)
typedef long long ll;
using namespace std;

const int inf = 1e9+10;
const int N = 100'010;

template<class T, class CMP>
struct rmq {
	static int constexpr lg = 18;
	CMP cmp;
	typedef pair<T,int> el;
	vector<el> vec[lg];
	int sz;

	el mn(const el &x, const el &y) { return cmp(x.first, y.first)? x: y; }

	void init(const vector<T> &a) {
		sz = a.size();
		vec[0].resize(sz);
		Loop (i,0,sz)
			vec[0][i] = {a[i], i};
		Loop (j,0,lg-1) {
			if ((2<<j) > sz)
				break;
			vec[j+1].resize(sz-(2<<j)+1);
			for (int i = 0; i + (2<<j) <= sz; ++i)
				vec[j+1][i] = mn(vec[j][i], vec[j][i+(1<<j)]);
		}
	}
	el get(int l, int r) {
		int k = __lg(r-l);
		return mn(vec[k][l], vec[k][r-(1<<k)]);
	}
};
rmq<int, less<int>> rmq_mn;
rmq<int, greater<int>> rmq_mx;

namespace seg {
	vector<int> t[4*N];
	int sz;

	void init(const vector<int> &vec, int i, int b, int e) {
		if (e-b == 1) {
			t[i] = {vec[b]};
			return;
		}
		init(vec, 2*i+1, b, (b+e)/2);
		init(vec, 2*i+2, (b+e)/2, e);
		t[i].resize(t[2*i+1].size() + t[2*i+2].size());
		merge(t[2*i+1].begin(), t[2*i+1].end(),
		      t[2*i+2].begin(), t[2*i+2].end(),
		      t[i].begin());
	}
	void init(const vector<int> &vec) { sz = vec.size(); init(vec, 0, 0, sz); }

	int get(int l, int r, int d, int i, int b, int e) {
		if (l <= b && e <= r)
			return t[i].end() - lower_bound(t[i].begin(), t[i].end(), d);
		if (r <= b || e <= l)
			return 0;
		return   get(l, r, d, 2*i+1, b, (b+e)/2)
		       + get(l, r, d, 2*i+2, (b+e)/2, e);
	}
	int get(int l, int r, int d) { return get(l, r, d, 0, 0, sz); }

	int lrmost(int l, int r, int d, bool dir, int i, int b, int e) {
		if (r <= b || e <= l || t[i].back() < d)
			return -1;
		if (e-b == 1)
			return b;
		int ans = -1;
		ans = lrmost(l, r, d, dir, 2*i+1+ dir, dir? (b+e)/2: b, dir? e: (b+e)/2);
		if (ans != -1)
			return ans;
		ans = lrmost(l, r, d, dir, 2*i+1+!dir, dir? b: (b+e)/2, dir? (b+e)/2: e);
		return ans;
	}
	int leftmost(int l, int r, int d) { return lrmost(l, r, d, 0, 0, 0, sz); }
	int rightmost(int l, int r, int d) { return lrmost(l, r, d, 1, 0, 0, sz); }
}

int height[N];
int lsml[N], rsml[N];
int lval[N], rval[N], val[N];
int n;

void init_sml()
{
	vector<int> vec;
	Loop (i,0,n) {
		while (vec.size() && height[vec.back()] > height[i])
			vec.pop_back();
		lsml[i] = vec.size()? vec.back(): -1;
		vec.push_back(i);
	}
	vec.clear();
	LoopR (i,0,n) {
		while (vec.size() && height[vec.back()] > height[i])
			vec.pop_back();
		rsml[i] = vec.size()? vec.back(): n;
		vec.push_back(i);
	}
}

void init_val()
{
	Loop (i,0,n) {
		lval[i] = lsml[i] == -1? inf: lsml[i] == i-1? 0: rmq_mx.get(lsml[i]+1, i+1).first - height[i];
		rval[i] = rsml[i] ==  n? inf: rsml[i] == i+1? 0: rmq_mx.get(i, rsml[i]).first - height[i];
		val[i] = min(lval[i], rval[i]);
	}
	seg::init(vector<int>(val, val+n));
}

bool darre(int l, int r, int d, int i)
{
	int val = min(lsml[i] < l? inf: lval[i], rsml[i] >= r? inf: rval[i]);
	return val >= d;
}

void init(int N, std::vector<int> H)
{
	n = N;
	Loop (i,0,n)
		height[i] = H[i];
	rmq_mx.init(H);
	rmq_mn.init(H);
	init_sml();
	init_val();
}

int max_towers(int L, int R, int D)
{
	++R;
	int ans = seg::get(L, R, D);
	if (ans == 0) {
		ans = 1;
		int p = rmq_mx.get(L, R).second;
		if (p != L && p != R-1) {
			int pl = rmq_mn.get(L, p).second;
			int pr = rmq_mn.get(p+1, R).second;
			if (darre(L, R, D, pl) && darre(L, R, D, pr))
				ans = 2;
		}
		return ans;
	}
	int pl = seg::leftmost(L, R, D);
	int pr = seg::rightmost(L, R, D);
	if (pl != L) {
		int pll = rmq_mx.get(L, pl).second;
		if (pll != L) {
			int plll = rmq_mn.get(L, pll).second;
			ans += darre(L, R, D, plll);
		}
	}
	if (pr != R-1) {
		int prr = rmq_mx.get(pr+1, R).second;
		if (prr != R-1) {
			int prrr = rmq_mn.get(prr+1, R).second;
			ans += darre(L, R, D, prrr);
		}
	}
	return ans;
}

• 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