Submission #625450

#	Time	Username	Problem	Language	Result	Execution time	Memory
625450		model_code	Radio Towers (IOI22_towers)	C++17	11 / 100	4065 ms	2260 KiB

towers

// failed/solution-fausta-tle.cpp
#include "towers.h"

#include <vector>

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
const int NN = 2e5 + 5;
int ma = 0, k, a[NN], n, kan[NN], nx[NN], d[NN], m;
int ST[4 * NN];
int BIT[3 * NN];

map<int, int> me;

void init(int N, std::vector<int> H) {
	n = N;
	for(int i = 0; i < N; i++)
	{
		a[i + 1] = H[i];
	}
}

int max_towers(int L, int R, int D) {
	L++;
	R++;
	long long ans = 0;
	for(int i = L; i <= R; i++)
	{
		kan[i] = R + 1;
		int X = i;
		if(i > L && a[i] <= a[i - 1])
			X = kan[i - 1] - 1;
		for(ll j = X + 1; j <= min(R, X + 1000); j++)
			if(a[j] <= a[i] - D)
			{
				kan[i] = j;
				break;
			}
		// for(ll j = max(X + 1, (X + 1 + n)/2 - 1000); j <= min(R, (X + 1 + n)/2 + 1000); j++)
		// 	if(a[j] <= a[i] - D)
		// 	{
		// 		kan[i] = j;
		// 		break;
		// 	}
		for(ll j = max(X + 1, X - 1000); j <= R; j++)
		{
			++ans;
			if(a[j] <= a[i] - D)
			{
				
				kan[i] = j;
				break;
			}
		}
	}
	// printf("%lld\n", ans);
	for(int i = L; i <= R; i++)
	{
		nx[i] = R + 1;
		for(int j = i + 1; j <= min((int)R, i + 2000); j++)
			if(a[j] >= a[i] + D)
				nx[i] = min(nx[i], kan[j]);
		for(int j = max(i + 1, (i+1+R)/2 - 2000); j <= min((int)R, (i+1+R)/2 + 2000); j++)
		{
			if(j > nx[i])
				break;
			if(a[j] >= a[i] + D)
				nx[i] = min(nx[i], kan[j]);
		}
		for(int j = max(i + 1, (int)R - 2000); j <= R; j++)
		{
			if(j > nx[i])
				break;
			if(a[j] >= a[i] + D)
				nx[i] = min(nx[i], kan[j]);
		}
	}
	d[R + 1] = 0;
	for(int i = R; i >= L; i--)
		d[i] = max(d[i + 1], 1 + d[nx[i]]);
	return d[L];
}


/*
7 1
10 20 60 30 50 40 70
1 5 10

7 3
10 20 60 30 50 40 70
1 5 10
2 2 100
0 6 17
*/

• 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