Submission #1286774

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286774		SmuggingSpun	Bitaro's travel (JOI23_travel)	C++20	100 / 100	343 ms	4560 KiB

travel

#include<bits/stdc++.h>
#define taskname "C"
using namespace std; 
typedef long long ll;
const int lim = 2e5 + 5;
int n, q, a[lim];
namespace sub12{
	void solve(){
		int s, p;
		cin >> s;
		ll ans = 0;
		for(int r = upper_bound(a + 1, a + n + 1, s) - a, l = r - 1, _ = 0; _ < n; _++){
			if(l == 0 || (r != n + 1 && s - a[l] > a[r] - s)){
				ans += a[r] - s;
				s = a[r++];
			}			
			else{
				ans += s - a[l];
				s = a[l--];
			}
		}
		cout << ans;
	}
}
namespace sub34{
	ll get(int l, int r, int p){
		if(l == 1){
			return a[n] - p;
		}
		if(r == n){
			return p - a[1];
		}
		if(p - a[l - 1] <= a[r + 1] - p){
			int i = lower_bound(a + 1, a + n + 1, (p << 1) - a[r + 1]) - a;
			return p - a[i] + get(i, r, a[i]);
		}
		int i = upper_bound(a + 1, a + n + 1, (p << 1) - a[l - 1]) - a - 1;
		return a[i] - p + get(l, i, a[i]);
	}
	void solve(){
		for(int _ = 0; _ < q; _++){
			int s;
			cin >> s;
			int p = lower_bound(a + 1, a + n + 1, s) - a;
			if(p < 2){
				cout << a[n] - s << "\n";
			}			
			else if(p == n + 1){
				cout << s - a[1] << "\n";
			}
			else if(a[p] - s < s - a[p - 1]){
				cout << get(p, p, a[p]) + a[p] - s << "\n";
			}
			else{
				cout << get(p - 1, p - 1, a[p - 1]) + s - a[p - 1] << "\n";
			}
		}
	}
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
	}
	cin >> q;
	if(q == 1){
		sub12::solve();
	}
	else{
		sub34::solve();
	}
}

Compilation message (stderr)

travel.cpp: In function 'int main()':
travel.cpp:63:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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