Submission #1056380

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056380		parsadox2	Radio Towers (IOI22_towers)	C++17	23 / 100	4073 ms	19388 KiB

towers

#include <bits/stdc++.h>
#include "towers.h"

using namespace std;

const int N = 1e5 + 10 , inf = 1e9 , Lg = 17;

int n , a[N] , rmxq[N][Lg] , rmnq[N][Lg] , lg2[N];

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;
}

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]);
		}
	}
}

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 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 , int val)
{
	if(l > r)
		return 0;
	int mn = a[Get_mn(l , r)];
	int pos_mx = Get_mx(l , r);
	if(mn > val)
		return 0;
	int res = max(1 , Solve(l , pos_mx - 1 , d , a[pos_mx] - d) + Solve(pos_mx + 1 , r , d , a[pos_mx] - d));
	return res;
}


int max_towers(int l , int r , int d)
{
	return Solve(l , r , d , inf);
}

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