Submission #1056752

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056752		parsadox2	Radio Towers (IOI22_towers)	C++17	58 / 100	574 ms	36344 KiB

towers

#include <bits/stdc++.h>
#include "towers.h"
#define F first
#define S second
using namespace std;
 
const int N = 1e5 + 10 , inf = 1e9 , Lg = 17;
 
int n , a[N] , rmxq[N][Lg] , rmnq[N][Lg] , lg2[N] , nexL[N] , nexR[N] , las;
int b[N] , psum[N] , m;
vector <int> all;
vector <pair<int , int>> good;
 
int mn_pos(int aa , int bb)
{
	if(a[aa] < a[bb])
		return aa;
	return bb;
}
 
int mx_pos(int aa , int bb)
{
	if(a[aa] > a[bb])
		return aa;
	return bb;
}
 
int Get_mx(int l , int r)
{
	r++;
	int sz = (r - l);  sz = lg2[sz];
	return mx_pos(rmxq[l][sz] , rmxq[r - (1 << sz)][sz]);
}
 
int Get_mn(int l , int r)
{
	r++;
	int sz = (r - l);  sz = lg2[sz];
	return mn_pos(rmnq[l][sz] , rmnq[r - (1 << sz)][sz]);
}


void Build()
{
	lg2[1] = 0;
	for(int i = 2 ; i < N ; i++)
		lg2[i] = lg2[i / 2] + 1;
	for(int i = 0 ; i < n ; i++)
		rmnq[i][0] = rmxq[i][0] = i;
	for(int j = 1 ; j < Lg ; j++)
	{
		int len = (1 << j);
		for(int i = 0 ; i + len <= n ; i++)
		{
			rmnq[i][j] = mn_pos(rmnq[i][j - 1] , rmnq[i + len / 2][j - 1]);
			rmxq[i][j] = mx_pos(rmxq[i][j - 1] , rmxq[i + len / 2][j - 1]);
		}
	}
	for(int i = 1 ; i + 1 < n ; i++)  if(a[i] > a[i - 1] && a[i] > a[i + 1])
		b[i] = 1;
	for(int i = 1 ; i < n ; i++)
		psum[i] = psum[i - 1] + b[i];
	vector <int> st;
	for(int i = 0 ; i < n ; i++)
	{
		nexL[i] = -1;
		nexR[i] = n;
		while(!st.empty())
		{
			if(a[st.back()] < a[i])
			{
				nexR[st.back()] = i;
				st.pop_back();
			}
			else
			{
				nexL[i] = st.back();
				break;
			}
		}
		st.push_back(i);
	}
	for(int i = 0 ; i < n ; i++)  if(i - nexL[i] > 1 && nexR[i] - i > 1)
	{
		int lc = Get_mn(nexL[i] + 1 , i - 1) , rc = Get_mn(i + 1 , nexR[i] - 1);
		all.push_back(a[i] - max(a[lc] , a[rc]));
	}
	sort(all.begin() , all.end());
}
 
void init(int nn , vector <int> vec)
{
	n = nn;
	for(int i = 0 ; i < n ; i++)
		a[i] = vec[i];
	Build();
}
 
int Solve(int l , int r , int d)
{
	if(l > r)
		return 0;
	int pos_mx = Get_mx(l , r);
	int res = Solve(l , pos_mx - 1 , d) + Solve(pos_mx + 1 , r , d);
	if(pos_mx != l && pos_mx != r)
	{
		int lc = Get_mn(l , pos_mx - 1) , rc = Get_mn(pos_mx + 1 , r);
		if(a[pos_mx] - a[lc] >= d && a[pos_mx] - a[rc] >= d)
			res++;
	}
	return res;
}

bool cmp(pair <int , int> aa , pair <int , int> bb)
{
	return aa.S < bb.S;
}

struct SEG
{
	vector <int> t[N << 2];
	int mx[N << 2] , mn[N << 2];
	void Build(int node = 1 , int nl = 0 , int nr = m)
	{
		t[node].clear();
		if(nr - nl == 1)
		{
			t[node].push_back(good[nl].F);
			mx[node] = good[nl].S;
			mn[node] = good[nl].S;
			return;
		}
		int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
		Build(lc , nl , mid);  Build(rc , mid , nr);
		t[node] = t[lc];
		for(auto u : t[rc])
			t[node].push_back(u);
		sort(t[node].begin() , t[node].end());
		mx[node] = max(mx[lc] , mx[rc]);
		mn[node] = min(mn[lc] , mn[rc]);
	}
	int Get(int l , int r , int node = 1 , int nl = 0 , int nr = m)
	{
		//cout << node << " " << nl << " " << nr << " " << mx[node] << endl;
		if(mx[node] <= r)
		{
			int id = lower_bound(t[node].begin() , t[node].end() , l) - t[node].begin();
			//cout << "WTF " << id << endl;
			return t[node].size() - id;
		}
		if(mn[node] > r)
			return 0;
		int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
		return Get(l , r , lc , nl , mid) + Get(l , r , rc , mid , nr);
	}
} seg;

void Prep(int d)
{
	good.clear();
	for(int i = 0 ; i < n ; i++)  if(i - nexL[i] > 1 && nexR[i] - i > 1)
	{
		int lc = Get_mn(nexL[i] + 1 , i - 1) , rc = Get_mn(i + 1 , nexR[i] - 1);
		int mx_d = a[i] - max(a[lc] , a[rc]);
		if(d > mx_d)
			continue;
		int low = nexL[i] + 1 , high = i;
		while(high - low > 1)
		{
			int mid = (low + high) >> 1;
			lc = Get_mn(mid , i - 1);
			if(a[i] - a[lc] >= d)
				low = mid;
			else
				high = mid;
		}
		int L = low;
		low = i;  high = nexR[i] - 1;
		while(high - low > 1)
		{
			int mid = (low + high) >> 1;
			rc = Get_mn(i + 1 , mid);
			if(a[i] - a[rc] >= d)
				high = mid;
			else
				low = mid;
		}
		int R = high;
		//cout << i << " " << d << " WTF " << L << " " << R << endl;
		good.push_back({L , R});
	}
	m = good.size();
	sort(good.begin() , good.end() , cmp);
	if(m != 0)
		seg.Build();
}
 
int max_towers(int l , int r , int d)
{
	if(d == 1)
	{
		if(l + 1 >= r)
			return 1;
		return 1 + psum[r - 1] - psum[l];
	}
	if(psum[r - 1] - psum[l] == 0)
		return 1;
	if(psum[r - 1] - psum[l] == 1)
	{
		int id = Get_mx(l , r);
		int lc = Get_mn(l , id - 1) , rc = Get_mn(id + 1 , r);
		if(a[id] - d >= a[lc] && a[id] - d >= a[rc])
			return 2;
		return 1;
	}
	if(l == 0 && r == n - 1)
	{
		int id = lower_bound(all.begin() , all.end() , d) - all.begin();
		return all.size() - id + 1;
	}
	if(las != d)
	{
		Prep(d);
		las = d;
	}
	if(las == d)
	{
		if(m == 0)
			return 1;
		return seg.Get(l , r) + 1;
	}
	return 1 + Solve(l , r , d);
}

• Subtask 1: 4 / 4
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 14 / 14
• Subtask 5: 17 / 17
• Subtask 6: 0 / 19
• Subtask 7: 0 / 23