Submission #630974

#	Time	Username	Problem	Language	Result	Execution time	Memory
630974		prvocislo	Radio Towers (IOI22_towers)	C++17	100 / 100	2130 ms	37300 KiB

towers

#include "towers.h"
#include <algorithm>
#include <iostream>
#include <vector>
typedef long long ll;
using namespace std;

const int maxn = 1 << 17, inf = 1e9 + 5;
struct node1 { int mi, mx, dix, dxi; node1() { mi = inf, mx = -inf, dix = 0, dxi = 0; } };
vector<node1> tmx(maxn * 2);
vector<int> h;
node1 merge(node1 l, node1 r)
{
	node1 n;
	n.mi = min(l.mi, r.mi);
	n.mx = max(l.mx, r.mx);
	n.dix = max({ l.dix, r.dix, r.mx - l.mi });
	n.dxi = max({ l.dxi, r.dxi, l.mx - r.mi });
	return n;
}
node1 query(int l, int r)
{
	node1 n1, n2;
	for (l += maxn, r += maxn + 1; l < r; l >>= 1, r >>= 1)
	{
		if (l & 1) n1 = merge(n1, tmx[l++]);
		if (r & 1) n2 = merge(tmx[--r], n2);
	}
	return merge(n1, n2);
}
struct node2 { int tim, mi, mx; };
bool cmp(node2 a, node2 b) { return a.tim < b.tim; }
bool cmp2(node2 a, int t) { return a.tim < t; }
vector<vector<node2> > tr(maxn * 2);
void update(int i, int t, int x)
{
	for (i += maxn; i > 0; i >>= 1) tr[i].push_back({ t, x, x });
}
void upd(int vr, int t, int& mi, int& mx, int& cnt)
{
	int i = lower_bound(tr[vr].begin(), tr[vr].end(), t, cmp2) - tr[vr].begin();
	if (i == tr[vr].size()) return;
	mi = min(mi, tr[vr][i].mi), mx = max(mx, tr[vr][i].mx), cnt += tr[vr].size() - i;
}
void query(int l, int r, int t, int& mi, int& mx, int& cnt)
{
	for (l += maxn, r += maxn + 1; l < r; l >>= 1, r >>= 1)
	{
		if (l & 1) upd(l++, t, mi, mx, cnt);
		if (r & 1) upd(--r, t, mi, mx, cnt);
	}
}
void init(int n, vector<int> H) 
{
	h = H;
	for (int i = 0; i < n; i++) tmx[maxn + i].mi = tmx[maxn + i].mx = h[i];
	for (int i = maxn - 1; i > 0; i--) tmx[i] = merge(tmx[(i << 1)], tmx[(i << 1) | 1]);
	vector<int> l(n, -1), r(n, n);
	vector<int> st;
	for (int i = 0; i < n; i++)
	{
		while (!st.empty() && h[st.back()] > h[i]) st.pop_back();
		if (!st.empty()) l[i] = st.back();
		st.push_back(i);
	}
	st.clear();
	for (int i = n - 1; i >= 0; i--)
	{
		while (!st.empty() && h[st.back()] > h[i]) st.pop_back();
		if (!st.empty()) r[i] = st.back();
		st.push_back(i);
	}
	for (int i = 0; i < n; i++)
	{
		int ml = (l[i] == -1 ? inf : query(l[i] + 1, i - 1).mx), mr = (r[i] == n - 1 ? inf : query(i + 1, r[i] - 1).mx);
		int t = max(0, min(ml - h[i], mr - h[i]));
		update(i, t, i);
	}
	for (int i = 0; i < maxn * 2; i++)
	{
		sort(tr[i].begin(), tr[i].end(), cmp);
		for (int j = (int)tr[i].size() - 2; j >= 0; j--) tr[i][j].mi = min(tr[i][j].mi, tr[i][j + 1].mi), tr[i][j].mx = max(tr[i][j].mx, tr[i][j + 1].mx);
	}
}
int max_towers(int l, int r, int d) 
{
	int lo = l, hi = r + 1;
	while (lo < hi) // chceme najst prvy index...
	{
		int m = (lo + hi) / 2;
		if (query(l, m).dix >= d) hi = m; // mozeme ist nizsie
		else lo = m + 1;
	}
	int li = lo;
	lo = l - 1, hi = r;
	while (lo < hi) // chceme najst posledny index...
	{
		int m = (lo + hi + 1) / 2;
		if (query(m, r).dxi >= d) lo = m; // mozeme ist vyssie
		else hi = m - 1;
	}
	int ri = lo;
	int mi = inf, mx = -inf, cnt = 0;
	query(l, r, d, mi, mx, cnt);
	if (cnt == 0) return 1 + (int)(li <= ri);
	if (query(li, mi).mx >= h[mi] + d) cnt++;
	if (query(mx, ri).mx >= h[mx] + d) cnt++;
	return cnt;
}

Compilation message (stderr)

towers.cpp: In function 'void upd(int, int, int&, int&, int&)':
towers.cpp:42:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node2>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |  if (i == tr[vr].size()) return;
      |      ~~^~~~~~~~~~~~~~~~

• 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