Submission #1181387

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181387		catch_me_if_you_can	Radio Towers (IOI22_towers)	C++20	11 / 100	242 ms	25028 KiB

towers

//lurker you should listen to https://www.youtube.com/watch?v=a3egbaw-VK4 ASAP

//Hofstadter's law: programming projects take longer than you expect, even when you take into account Hofstadter's law

#include<bits/stdc++.h>
#include "towers.h"
using namespace std;
#define in array<int, 2>
#define pb push_back
#define pob pop_back

const int MX = 1e5+5;
const int INF = 2e9;
const int LOGM = 18; 

int n;

vector<int> a(MX);
vector<int> lo_w(MX);
vector<int> hi_w(MX);
vector<int> nxt_lo(MX);//next optimal descent.
vector<int> nxt_hi(MX);//next optimal ascent.
vector<int> clow(MX);

int LO[LOGM][MX];
int HI[LOGM][MX];

int Nxt[LOGM][MX];

bool rinited = false;

void init(int N, vector<int> h)
{
	n = N;
	rinited = false;
	for(int i = 1; i <= n; i++)
		a[i] = h[i-1];
	vector<int> lo(n+2);//immediate next dip
	vector<int> hi(n+2);//immediate next up
	//vector<int> lo_w(n+1);//suppose a[i], >a[i], >a[i] ..., < a[i]. largest "value" among the next few vals
	//vector<int> hi_w(n+1);//same as above, smallest value among the next few vals
	for(int i = 1; i <= n; i++)
		lo[i] = hi[i] = i+1;

	a[n+1] = -INF; LO[0][n] = LO[0][n+1] = n+1;
	for(int i = n; i >= 1; i--)
	{
		lo_w[i] = a[i];
		while(a[lo[i]] > a[i])
		{
			lo_w[i] = max(lo_w[i], lo_w[lo[i]]);
			lo[i] = lo[lo[i]];
		}
		LO[0][i] = lo[i];
	}
	a[n+1] = +INF; HI[0][n] = HI[0][n+1] = n+1; 
	for(int i = n; i >= 1; i--)
	{
		hi_w[i] = a[i];
		while(a[hi[i]] < a[i])
		{
			hi_w[i] = min(hi_w[i], hi_w[hi[i]]);
			hi[i] = hi[hi[i]];
		}
		HI[0][i] = hi[i];
	}
	for(int i = 1; i <= n; i++)
	{
		lo_w[i] = lo_w[i] - a[i];
		hi_w[i] = a[i] - hi_w[i];
	}
	for(int k = 1; k < LOGM; k++)
	{
		for(int i = 1; i <= n+1; i++)
			LO[k][i] = LO[k-1][LO[k-1][i]];
		for(int i = 1; i <= n+1; i++)
			HI[k][i] = HI[k-1][HI[k-1][i]];
	}
	/*cout << "Debugging vals: " << endl;
	for(int i = 1; i <= n; i++)
		cout << lo_w[i] << " ";
	cout << endl;
	for(int i = 1; i <= n; i++)
		cout << hi_w[i] << " ";
	cout << endl;*/
	return;
}

void r_init(int D)
{
	if(rinited)
		return;
	rinited = true;
	vector<int> sp_lo(n+2, n+1);
	vector<int> sp_hi(n+2, n+1);
	clow.assign(n+2, n+1);
	for(int i = n; i >= 1; i--)
	{
		if(lo_w[i] >= D)
			sp_lo[i] = i;
		else
			sp_lo[i] = sp_lo[LO[0][i]];
		
		clow[i] = sp_lo[i];
		
		if(hi_w[i] >= D)
			sp_hi[i] = i;
		else
			sp_hi[i] = sp_hi[HI[0][i]];
	}
	for(int i = 1; i <= n; i++)
	{
		//cout << "Currently computing optimal jumps for i = " << i << endl;
		int u = i;
		a[n+1] = INF;
		for(int k = LOGM-1; k >= 0; k--)
		{
			if(a[HI[k][u]] < (D+a[i]))
				u = HI[k][u];
		}
		u = HI[0][u];
		//cout << "First worker = " << u << endl;
		//now u is the smallest active fellow after i.
		int j = sp_hi[u];
		//cout << "- First jump should go to " << j << endl;
		if(j == (n+1))
		{
			Nxt[0][i] = n+1;
			continue;
		}
		a[n+1] = -INF;
		u = j;
		for(int k = LOGM-1; k >= 0; k--)
		{
			if(a[LO[k][u]] > (a[j]-D))
				u = LO[k][u];
		}
		u = LO[0][u];
		//cout << "Ended at " << u << endl;
		int ip = sp_lo[u];
		Nxt[0][i] = ip;
		if((ip) == (n+1))
			Nxt[0][i] = u;
		//cout << "--- Next jump should go to " << Nxt[0][i] << endl;
	}
	Nxt[0][n+1] = n+1;
	for(int k = 1; k < LOGM; k++)
	{
		for(int i = 1; i <= (n+1); i++)
		{
			Nxt[k][i] = Nxt[k-1][Nxt[k-1][i]]; 
			//cout << Nxt[k][i] << " ";
		}
		//cout << endl;
	}
	return;
}

int max_towers(int L, int R, int D)
{
	L++; R++;
	r_init(D);
	if(clow[L] > R)
		return 1;
	int ans = 1;
	int u = clow[L];
	//cout << "For optimal results, we should start at u = " << u << endl; 
	for(int k = LOGM-1; k >= 0; k--)
	{
		if(Nxt[k][u] <= R)
		{
			u = Nxt[k][u];
			//cout << "I jumped to " << u << endl;
			ans+=((1ll<<k));
		}
	}
	return ans;
}

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