Submission #749906

#	Time	Username	Problem	Language	Result	Execution time	Memory
749906		Cyber_Wolf	Bitaro's travel (JOI23_travel)	C++17	100 / 100	448 ms	8056 KiB

travel

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("Ofast")

using namespace std;
using namespace __gnu_pbds;

#define lg long long
#define ordered_set	tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

int main()
{
	fastio;
	lg n;
	cin >> n;
	vector<lg> v(n+2);
	for(int i = 1; i <= n; i++)	cin >> v[i];
	v[0] = -1e15, v[n+1] = 1e15;
	lg q;
	cin >> q;
	while(q--)
	{
		lg x;
		cin >> x;
		lg idx = 1;
		lg l1 = 1, r1 = n;
		while(l1 <= r1)
		{
			lg mid = (l1+r1)/2;
			if(v[mid] >= x)
			{
				idx = mid;
				r1 = mid-1;
			}
			else	l1 = mid+1;
		}
		lg idx2 = 1;
		l1 = 1, r1 = n;
		while(l1 <= r1)
		{
			lg mid = (l1+r1)/2;
			if(v[mid] <= x)
			{
				idx2 = mid;
				l1= mid+1;
			}
			else	r1 = mid-1;
		}
		if(abs(v[idx2]-x) <= abs(v[idx]-x))	idx = idx2;
		lg ans = abs(v[idx]-x);
		lg l = idx, r = idx;
		while(l > 1 || r < n)
		{
			if(v[r+1]-v[idx] < v[idx]-v[l-1])
			{
				l1 = r+1, r1 = n;
				lg cur = 1;
				while(l1 <= r1)
				{
					lg mid1 = (l1+r1)/2;
					if(v[mid1] < 2*v[idx]-v[l-1])
					{
						l1 = mid1+1;
						cur = mid1;
					}
					else	r1 = mid1-1;
				}
				ans += abs(v[cur]-v[idx]);
				idx = cur;
				l = min(l, idx);
				r = max(r, idx);
			}
			else{
				l1 = 1, r1 = l-1;
				lg cur = 1;
				while(l1 <= r1)
				{
					lg mid1 = (l1+r1)/2;
					if(v[mid1] >= 2*v[idx]-v[r+1])
					{
						r1 = mid1-1;
						cur = mid1;
					}
					else	l1 = mid1+1;
				}
				ans += abs(v[cur]-v[idx]);
				idx = cur;
				l = min(l, idx);
				r = max(r, idx);
			}
		}
		cout << ans << '\n';
	}

    return 0;
}

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