Submission #800391

#	Time	Username	Problem	Language	Result	Execution time	Memory
800391		MadokaMagicaFan	Radio Towers (IOI22_towers)	C++17	100 / 100	2135 ms	127036 KiB

towers

#include "bits/stdc++.h"

using namespace std;
using ll = long long;

#define sz(v) ((int)(v).size())
#define pb push_back

int n;
vector<int> h;
const int inf = 1e9+7;

struct aint {
	int n, neut;
	vector<int> f;
	int (*fn)(const int, const int);

	aint(int _n, int _neut, int (*_fn)(const int, const int)) {
		n = _n; neut = _neut;
		fn = _fn;
		f.assign(n<<1, neut);
	}

	int
	query(int l, int r)
	{
		int res = neut;
		for (l += n, r+=n+1; l < r; l>>=1, r>>=1) {
			if (l&1) res = fn(res, f[l++]);
			if (r&1) res = fn(res, f[--r]);
		}
		return res;
	}

	void
	upd(int x, int v) {
		x+=n;
		for (f[x] = v; x > 1; x>>=1) {
			f[x>>1] = fn(f[x], f[x^1]);
		}
	}
};

struct paint {
	int n, neut;
	int (*fn)(const int, const int);
	vector<array<int, 3>> f; /* val, l, r */
	int cn = 0;

	paint(int _n, int _neut, int (*_fn)(const int, const int))
	{
		fn = _fn;
		n = _n; neut = _neut;

		f.assign(max(20*n, (int)2e5), {neut, -1, -1});
	}

	void chkalloc() {if (cn == sz(f)) f.resize(sz(f)+max(n, 100)); }

	int newv(int val) {
		chkalloc();
		f[cn] = {val, -1, -1};
		return cn++;
	}

	int newv(int l, int r) {
		chkalloc();
		f[cn] = {fn(f[l][0], f[r][0]), l, r};
		return cn++;
	}

	int build(int l, int r) {
		if (l == r)
			return newv(neut);
		int tm = (l+r)>>1;
		return newv(build(l, tm), build(tm+1, r));
	}

	int query(int i, int l, int r) { return query(i, 0, n-1, l, r); }

	int query(int i, int l, int r, int tl, int tr) {
		if (l >= tl && r <= tr) return f[i][0];
		if (r < tl || l >= tr) return neut;
		assert(i >= 0);

		int m = (r + l) >> 1;
		return fn(query(f[i][1], l, m, tl, tr), query(f[i][2], m+1, r, tl, tr));
	}

	int upd(int i, int x, int v) { return upd(i, 0, n-1, x, v); }

	int upd(int i, int l, int r, int x, int v) {
		if (l == r) return newv(v);
		int m = (l + r)>>1;

		if (x <= m)
			return newv(upd(f[i][1], l, m, x, v), f[i][2]);
		else
			return newv(f[i][1], upd(f[i][2], m+1, r, x, v));
	}
};

aint *tmnh, *tmxh;
paint *p1, *p2, *p3; /* p1 = sum; p2 = left pos; p3 = right pos */
map<int, int> hpos, dind;
vector<array<int, 3>> edg;
set<int> deltas;

const int N = 1e5;
int ip1[N+5], ip2[N+5], ip3[N+5];
int ev[N+5];

int mn(int a, int b) { return min(a, b); }
int mx(int a, int b) { return max(a, b); }
int sm(int a, int b) { return a + b; }


int
max_towers(int l, int r, int d)
{
	if (l == r) return 1;
	if (l + 1 == r) return 1;

	auto it = deltas.lower_bound(d);
	if (it == deltas.end()) return 1;

	int x = dind[*it];

	int ans = 0;

	int v, z, u = p2->query(ip2[x], l, r);
	if (u <= r && u > l) {
		z = hpos[tmnh->query(l, u-1)];
		v = hpos[tmxh->query(l, u-1)];
		l = u;
		if (h[u] - h[z] >= d)
			++ans;
	}

	u = p3->query(ip3[x], l, r);
	if (u < r && u >= l) {
		z = hpos[tmnh->query(u+1, r)];
		v = hpos[tmxh->query(u+1, r)];
		r = u;
		if (h[u] - h[z] >= d)
			++ans;
	}

	if (l > r) return ans;
	ans += p1->query(ip1[x], l, r);

	return max(ans, 1);
}

void
dfs(int x, int l, int r) {
	int y, z;
	if (l == r) return;

	if (x > l)  {
		y = tmnh->query(l, x-1);
		z = hpos[tmxh->query(l, x-1)];

		edg.pb({h[x] - y, x, z});
		dfs(z, l, x-1);
	}

	if (x < r) {
		y = tmnh->query(x+1, r);
		z = hpos[tmxh->query(x+1, r)];

		edg.pb({h[x] - y, x, z});
		dfs(z, x+1, r);
	}
}

void
init(int _n, std::vector<int> _h)
{
	n = _n;
	h = _h;

	tmnh = new aint(n, inf+10, mn);
	tmxh = new aint(n, -1, mx);
	for (int i = 0; i < n; ++i) {
		tmnh->upd(i, h[i]);
		tmxh->upd(i, h[i]);
		hpos[h[i]] = i;
	}

	dfs(hpos[tmxh->query(0, n-1)], 0, n-1);

	sort(edg.begin(), edg.end());
	reverse(edg.begin(), edg.end());

	for (auto x : edg) {
		deltas.insert(x[0]);
		ev[x[2]] = x[0];
		dind[x[0]] = sz(deltas);
	}

	p1 = new paint(n, 0, sm);
	p2 = new paint(n, inf, mn);
	p3 = new paint(n, -1, mx);

	int lp1, lp2, lp3;
	lp1 = p1->build(0, n-1);
	lp2 = p2->build(0, n-1);
	lp3 = p3->build(0, n-1);

	for (auto x : edg) {
		lp1 = p1->upd(lp1, x[1], 0);
		lp1 = p1->upd(lp1, x[2], 1);

		if (x[1] < x[2]) {
			lp2 = p2->upd(lp2, x[1], x[1]);
		} else {
			lp3 = p3->upd(lp3, x[1], x[1]);
		}
		ip1[dind[x[0]]] = lp1;
		ip2[dind[x[0]]] = lp2;
		ip3[dind[x[0]]] = lp3;
	}
}

Compilation message (stderr)

towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:131:6: warning: variable 'v' set but not used [-Wunused-but-set-variable]
  131 |  int v, z, u = p2->query(ip2[x], l, 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