Submission #897275

#	Time	Username	Problem	Language	Result	Execution time	Memory
897275		Hakiers	Bitaro's travel (JOI23_travel)	C++17	0 / 100	30 ms	13644 KiB

travel

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int BASE = 1 << 18;
constexpr int oo = 2e9;
pair<int, int> TREE[BASE<<1][2];	//0 to z lewej/ 1 z prawej
set<int> S;
vector<pair<int, int>> queries;
ll ans[BASE];
int nxt[BASE][2]; //0 to z lewej/ 1 z prawej
int a[BASE];
int n, q;

void update(int v, pair<int, int> val, bool c){
	v += BASE;
	TREE[v][c] = val;
	v/=2;
	while(v > 0){
		if(!c) TREE[v][c] = min(TREE[2*v][c], TREE[2*v+1][c]);
		else TREE[v][c] = max(TREE[2*v][c], TREE[2*v+1][c]);
		v/=2;
	}
}

void compute(){
	//z lewej
	for(int i = 1; i < n; i++){
		int roznica = a[i+1] - a[i];
		auto it = S.lower_bound((a[i]-roznica));
		
		nxt[i][0] = (*it);
	}
	nxt[n][0] = a[1];
	
	//z prawej
	for(int i = n; i > 1; i--){
		int roznica = a[i] - a[i-1];
		auto it = S.lower_bound((a[i]+roznica-1));
		if((*it) >= a[i]+roznica) --it;
		
		nxt[i][1] = (*it);
	}
	nxt[1][1] = a[n];
	
	
	nxt[0][0] = oo;
	for(int i = n+1; i < BASE; i++)
		nxt[i][0] = oo;
	
	for(int i = 0; i < BASE; i++)
		update(i, {nxt[i][0], a[i]}, 0);
}

int wsk = 1;
void przesun(int x){
	while(x > a[wsk]){
		update(wsk, {oo, 0}, 0);
		update(wsk, {nxt[wsk][1], a[wsk]}, 1);
		wsk++;
	}
	if(x == a[wsk])
		update(wsk, {nxt[wsk][1], a[wsk]}, 1);
}

pair<int, int> leftquery(int v, int l, int r, int x){ //chcemy sc jak najbardziej w lewo
	if(l == r) return TREE[v][0];
	
	int mid = (l+r)/2;
	if(TREE[2*v][0].first < x || TREE[2*v][0].first == a[1])
		return leftquery(2*v, l, mid, x);
	return leftquery(2*v+1, mid+1, r, x);
}

pair<int, int> rightquery(int v, int l, int r, int x){ // chcemy isc jak najbardziej w prawo
	if(l == r) return TREE[v][1];
	
	int mid = (l+r)/2;
	if(TREE[2*v+1][1].first > x || TREE[2*v+1][1].first == a[n])
		return rightquery(2*v+1, mid+1, r, x);
	return rightquery(2*v, l, mid, x);
}

ll check(int x){
	int l = x, r = x, act = x;
	ll res = 0;
	
	if(x-a[wsk-1] <= a[wsk]-x){
		l = a[wsk-1];
		act = l;
		res += x - a[wsk-1];
	}
	else{
		r = a[wsk];
		act = r;
		res += a[wsk]-x;
	}
	
	//cout << "x " << x << "\n";
	bool strona = 0;
	while(l > a[1] || r < a[n]){
		pair<int, int> tmp;
		if(!strona){
			tmp = leftquery(1, 0, BASE-1, l);
			res += abs(tmp.second-act);
			res += abs(tmp.second - tmp.first);
			act = tmp.first;
			r = max(r, tmp.second);
			l = min(l, tmp.first);
		}
		else{
			tmp = rightquery(1, 0, BASE-1, r); 
			res += abs(tmp.second-act);
			res += abs(tmp.second - tmp.first);
			act = tmp.first;
			r = max(r, tmp.first);
			l = min(l, tmp.second);
		}
		//cout << "l : " << l << " r: " << r << " RES : " << res << "\n";
		strona ^= 1;
	}
	//cout << "\n";

	return res;
}

void solve(){
	for(auto [u, idx] : queries){
		przesun(u);
		ans[idx] = check(u);
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	
	a[0] = -oo;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		S.insert(a[i]);
	}
	
	compute();
	cin >> q;
	
	for(int i = 1; i <= q; i++){
		int x;
		cin >> x;
		queries.push_back({x, i});
	}
	sort(queries.begin(), queries.end());
	
	/*
	for(int i = 1; i <= n; i++)
		cout << nxt[i][0] << " ";
		cout << "\n";
	for(int i = 1; i <= n; i++)
		cout << nxt[i][1] << " ";
	cout << "\n";
	*/
	solve();
	
	for(int i = 1; i <= q; i++)
		cout << ans[i] << "\n";
	
}

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