Submission #1308466

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308466		minh30082008	Bitaro's travel (JOI23_travel)	C++20	100 / 100	330 ms	61176 KiB

travel

#include<bits/stdc++.h>
#define fi first
#define se second
#define FOR(i, k, n) for(int i = k; i <= n; i++)
#define FOR1(i, k, n) for(int i = k; i >= n; i--)
#define pb push_back
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define vi vector<int>
#define pii pair<int, int>
#define vii vector<pii>
#define ll long long
#define vll vector<ll>
#define pll pair<ll, ll>
#define re return 0
#define mii map<int, int>
#define input "ALONE.inp"
#define output "ALONE.out"
#define rf 	freopen(input, "r", stdin); freopen(output, "w", stdout)
#define int ll
using namespace std;
const int maxn = 2e5 + 5;
const int mod = 1e9 + 7;
const int base = 998244353;
const int base1 = 31;
const int SZ = 320;
const ll INF = 1e18;
void add(int &a, int b) 
{
	a += b; 
	if(a >= mod) a -= mod; 
	if(a < 0) a += mod; 
}
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r)
{
	return uniform_int_distribution<int>(l, r) (rd);
}
int a[maxn];
int leftid[maxn], rightid[maxn];
int maxr[20][maxn], minl[20][maxn];
int lg[maxn];
int get_minl(int l, int r)
{
	int k = lg[r - l + 1];
	return min(minl[k][l], minl[k][r - (1 << k) + 1]);
}
int get_maxr(int l, int r)
{
	int k = lg[r - l + 1];
	return max(maxr[k][l], maxr[k][r - (1 << k) + 1]);
}
signed main()
{
	fastio;
	int n;
	cin >> n;
	FOR(i, 1, n)
		cin >> a[i];
	sort(a + 1, a + 1 + n);
	a[0] = -2e9;
	a[n + 1] = 2e9;
	FOR(i, 1, n)
	{
		int d = a[i + 1] - a[i];
		int l = 1, r = i;
		while(l <= r)
		{
			int mid = (l + r) >> 1;
			if(a[i] - a[mid] <= d)
			{
				leftid[i] = mid;
				r = mid - 1;
			}
			else
				l = mid + 1;
		}
	}
	FOR(i, 1, n)
		lg[i] = __lg(i);
	FOR(i, 1, n)
	{
		int d = a[i] - a[i - 1];
		int l = i, r = n;
		while(l <= r)
		{
			int mid = (l + r) >> 1;
			if(a[mid] - a[i] < d)
			{
				rightid[i] = mid;
				l = mid + 1;
			}
			else
				r = mid - 1;
		}
	}
	FOR(i, 1, n)
	{
		minl[0][i] = leftid[i];
		maxr[0][i] = rightid[i];
	}
	FOR(j, 1, 18)
		FOR(i, 1, n - (1 << j) + 1)
		{
			minl[j][i] = min(minl[j - 1][i], minl[j - 1][i + (1 << (j - 1))]);
			maxr[j][i] = max(maxr[j - 1][i], maxr[j - 1][i + (1 << (j - 1))]);
		}
	int q;
	cin >> q;
	while(q--)
	{
		int x;
		cin >> x;
		if(x >= a[n])
		{
			cout << x - a[1] << "\n";
			continue;
		}
		if(x <= a[1])
		{
			cout << a[n] - x << "\n";
			continue;
		}
		int left = -1, right = -1;
		int l = 1, r = n;
		while(l <= r)
		{
			int mid = (l + r) >> 1;
			if(a[mid] <= x)
			{
				left = mid;
				l = mid + 1;
			}
			else
				r = mid - 1;
		}
		l = 1, r = n;
		while(l <= r)
		{
			int mid = (l + r) >> 1;
			if(a[mid] >= x)
			{
				right = mid;
				r = mid - 1;
			}
			else
				l = mid + 1;
		}
		ll ans = 0;
		int huong, toado;
		if(x - a[left] <= a[right] - x)
			ans = x - a[left], toado = a[left];
		else
			ans = a[right] - x, toado = a[right];
		while(a[right] == toado)
			right++;
		while(a[left] == toado)
			left--;
		if(toado - a[left] <= a[right] - toado)
			huong = 0;
		else
			huong = 1;
		while(left > 0 || right <= n)
		{
			if(huong == 0)
			{
				l = 1, r = left;
				int vt = 1;
				while(l <= r)
				{
					int mid = (l + r) >> 1;
					if(get_maxr(mid, left) >= right)
					{
						vt = mid;
						l = mid + 1;
					}
					else
						r = mid - 1;
				}
				ans += toado - a[vt];
				toado = a[vt];
				left = vt - 1;
				if(right <= n)
				{
					ans += a[right] - a[vt];
					toado = a[right];
				}
				huong = 1;
			}
			else
			{
				l = right, r = n;
				int vt = n;
				while(l <= r)
				{
					int mid = (l + r) >> 1;
					if(get_minl(right, mid) <= left)
					{
						vt = mid;
						r = mid - 1;
					}
					else
						l = mid + 1;
				}
				ans += a[vt] - toado;
				toado = a[vt];
				right = vt + 1;
				if(left > 0)
				{
					ans += a[vt] - a[left];
					toado = a[left];
				}
				huong = 0;
			}
		}
		cout << ans << "\n";
	}
	re;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 55 / 55