Submission #1244218

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244218		amine_aroua	송신탑 (IOI22_towers)	C++20	23 / 100	4046 ms	6484 KiB

towers

#include "towers.h"

#include <bits/stdc++.h>
using namespace std;


vector<int> h;
int n;
vector<vector<int>> adj;
vector<int> tree;
vector<int> Tree;
int nN = 0;
void init(int N, std::vector<int> H) 
{
	n = N;
	h = H;
	adj.assign(n , {});
	while(__builtin_popcount(N) != 1)
	{
		N++;
		h.push_back(0);
	}
	tree.assign(2 * N , 0);
	for(int i = 0 ; i < N ; i++)
	{
		tree[i + N] = h[i];
	}
	Tree = tree;
	for(int i = N - 1 ; i >= 1 ; i--)
	{
		tree[i] = max(tree[i<<1] , tree[i<<1|1]);
		Tree[i] = min(Tree[i<<1] , Tree[i<<1|1]);
	}
	nN = N;
}

int walkgr(int node , int s , int e , int i , int x)
{
	if(i > e)
		return -1;
	if(tree[node] < x)
		return -1;
	if(s == e)
		return e;
	int md = (s + e)>>1;
	int lt = walkgr(node<<1 , s , md , i , x);
	if(lt == -1)
		return walkgr(node<<1|1 , md + 1 , e , i , x);
	else
		return lt;
}

int fr_greater_than(int i , int x)
{
	return walkgr(1 , 0 , nN - 1, i , x);
}

int walkle(int node , int s , int e , int i , int x)
{
	if(i > e)
		return -1;
	if(Tree[node] > x)
		return -1;
	if(s == e)
		return e;
	int md = (s + e)>>1;
	int lt = walkle(node<<1 , s , md , i , x);
	if(lt == -1)
		return walkle(node<<1|1 , md + 1 , e , i , x);
	else
		return lt;
}

int fr_less_than(int i , int x)
{
	return walkle(1 , 0 , nN - 1, i , x);
}

int walkgr0(int node , int s , int e , int i , int x)
{
	if(i < s)
		return -1;
	if(tree[node] < x)
		return -1;
	if(s == e)
		return e;
	int md = (s + e)>>1;
	int lt = walkgr0(node<<1|1 , md + 1 , e , i , x);
	if(lt == -1)
		return walkgr0(node<<1 , s , md , i , x);
	else
		return lt;
}

int lst_greater_than(int i , int x)
{
	return walkgr0(1 , 0 , nN - 1, i , x);
}

int walkle0(int node , int s , int e , int i , int x)
{
	if(i < s)
		return -1;
	if(Tree[node] > x)
		return -1;
	if(s == e)
		return e;
	int md = (s + e)>>1;
	int lt = walkle0(node<<1|1 , md + 1 , e , i , x);
	if(lt == -1)
		return walkle0(node<<1 , s , md , i , x);
	else
		return lt;
}

int lst_less_than(int i , int x)
{
	return walkle0(1 , 0 , nN - 1, i , x);
}

int max_towers(int L, int R, int D) 
{
	vector<int> nxt(n , n);
	for(int i = 0 ; i < n ; i++)
	{
		int k = fr_greater_than(i , h[i] + D);
		// cout<<i<<" : "<<k<<'\n';
		if(k == -1)
			continue;
		int j = fr_less_than(k , h[i]);
		if(j  == -1)
			continue;
		nxt[i] = j;
	}
	for(int i = 0 ; i < n ; i++)
	{
		int k = lst_greater_than(i , h[i] + D);
		// cout<<i<<" : "<<k<<'\n';
		if(k == -1)
			continue;
		int j = lst_less_than(k , h[i]);
		// cout<<i<<" : "<<j<<'\n';
		if(j == -1)
			continue;
		nxt[j] = min(nxt[j] , i);
	}
	// for(int i = 0 ; i <n ; i++)
	// 	cout<<nxt[i]<<'\n';
	vector<int> dp(n+1,0);
	for(int i = R ; i >= L ; i--)
	{
		dp[i] = dp[nxt[i]] + 1;
		dp[i] = max(dp[i] , dp[i + 1]);
	}
	return dp[L];
}

• 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