Submission #1175772

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175772		thelegendary08	Bitaro's travel (JOI23_travel)	C++17	100 / 100	233 ms	57440 KiB

travel

#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define int long long
#define vi vector<int>
#define vvi vector<vector<int>>
#define pii pair<int, int>
#define vpii vector<pair<int, int>>
#define vc vector<char>
#define vb vector<bool>
#define mii map<int,int>
#define f0r(i,n) for(int i=0;i<n;i++)
#define FOR(i,k,n) for(int i=k;i<n;i++)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define in(a) int a; cin>>a
#define in2(a,b) int a,b; cin>>a>>b
#define in3(a,b,c) int a,b,c; cin>>a>>b>>c
#define in4(a,b,c,d) int a,b,c,d; cin>>a>>b>>c>>d
#define vin(v,n); vi v(n); f0r(i,n){cin>>v[i];}
#define out(a) cout<<a<<'\n'
#define out2(a,b) cout<<a<<' '<<b<<'\n'
#define out3(a,b,c) cout<<a<<' '<<b<<' '<<c<<'\n'
#define out4(a,b,c,d) cout<<a<<' '<<b<<' '<<c<<' '<<d<<'\n'
#define pout(a) cout<<a.first<<' '<<a.second<<'\n'
#define vout(v) for(auto u : v){cout<<u<<' ';} cout<<'\n'
#define dout(a) cout<<a<<' '<<#a<<'\n'
#define dout2(a,b) cout<<a<<' '<<#a<<' '<<b<<' '<<#b<<'\n'
#define yn(x); if(x){cout<<"YES"<<'\n';}else{cout<<"NO"<<'\n';}
const int leg = 1e9 + 7;
const int mod = 998244353;
using namespace std;
const int mxn = 2e5 + 5;
vi pv(mxn), nxt(mxn), pvd, nxtd;
vvi tree(mxn * 4, vi(2));
void build(int v, int l, int r, int d, vi &a){
	if(l == r){
		tree[v][d] = a[l];
		return;
	}
	int mid = (l + r) / 2;
	build(v * 2, l, mid, d, a);
	build(v * 2 + 1, mid + 1, r, d, a);
	if(d == 0){
		tree[v][d] = min(tree[v*2][d], tree[v*2+1][d]);
	}
	else tree[v][d] = max(tree[v*2][d], tree[v*2+1][d]);
}
int first_leq(int v, int tl, int tr, int l, int r, int b){
	if(tl > r || tr < l)return -1; 
	if(tree[v][0] > b)return -1;
	if(tl == tr)return tl;
	int tm = (tl + tr) / 2;
	int left = first_leq(v*2, tl, tm, l, r, b);
	if(left == -1) return first_leq(v * 2 + 1, tm + 1, tr, l, r, b);
	else return left;
}
int first_greater(int v, int tl, int tr, int l, int r, int b){
	if(tl > r || tr < l)return -1;
	if(tree[v][1] <= b)return -1;
	if(tl == tr)return tl;
	int tm = (tl + tr) / 2;
	int right = first_greater(v*2+1, tm + 1, tr, l, r, b);
	if(right == -1)return first_greater(v*2, tl, tm, l, r, b);
	else return right;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	//ifstream cin(".in");
	//ofstream cout(".out");
	in(n);
	pvd.resize(n);
	nxtd.resize(n);
	vin(v,n);
	f0r(i,n-1){
		nxt[i] = v[i+1];
		pv[i+1] = v[i];
		nxtd[i] = v[i+1] - v[i];
		pvd[i+1] = v[i+1] - v[i];
	}
	nxtd[n-1] = 1e18;
	pvd[0] = 1e18;
	vi mint(n), maxt(n);
	f0r(i,n){
		mint[i] = v[i] - nxtd[i];
		maxt[i] = v[i] + pvd[i];
	}
	build(1, 0, n-1, 0, mint);
	build(1, 0, n-1, 1, maxt);
	
	in(q);
	f0r(i,q){
		in(x);
		int ans = 0;
		
		//find point to the left of x
		int lo = -1;
		int hi = n-1;
		while(lo < hi){
			int mid = lo + (hi - lo + 1) / 2;
			if(v[mid] <= x){
				lo = mid;
			}
			else{
				hi = mid - 1;
			}
		}
		
		//find first visited point. l and r store range of indices already visited
		int dir; //left = 0, right = 1
		int LEFT = 0; 
		int RIGHT = 1;
		int l, r;
		if(lo == -1){
			ans += v[0] - x;
			l = 0; r = 0; dir = RIGHT;
		}
		else{
			if(v[lo] == x){
				l = lo; r = lo;
				if(lo == n - 1)dir = LEFT;
				else if(lo == 0)dir = RIGHT;
				else{
					if(v[lo + 1] - x < x - v[lo - 1])dir = RIGHT;
					else dir = LEFT;
				}
			}
			else if(lo == n - 1){
				ans += x - v[n-1];
				l = n - 1; r = n - 1; dir = LEFT;
			}
			else{
				int ld = x - v[lo];
				int rd = v[lo+1] - x;
				if(ld <= rd){
					x = v[lo];
					l = lo; r = lo; ans += ld;
					if(lo == n - 1)dir = LEFT;
					else if(lo == 0)dir = RIGHT;
					else{
						if(v[lo + 1] - x < x - v[lo - 1])dir = RIGHT;
						else dir = LEFT;
					}
				}
				else{
					x = v[lo + 1];
					l = lo + 1; r = lo + 1; ans += rd; 
					if(lo + 1 == n - 1)dir = LEFT;
					else if(lo + 1 == 0)dir = RIGHT;
					else{
						if(v[lo + 2] - x < x - v[lo])dir = RIGHT;
						else dir = LEFT;
					}
				}
			}
		}
		
		//find turning point until completion
		int cur = l; // current index
		while(l != 0 || r != n-1){
			// out3(dir,l,r);
			if(l == 0){
				r = n-1;
				ans += v[n-1] - v[0];
			}
			else if(r == n-1){
				l = 0;
				ans += v[n-1] - v[0];
			}
			else{
				if(dir == RIGHT){
					int a = v[l];
					int b = pv[l];
					//bsta on segtree 1, first one <= b, starting from r + 1.
					int c = first_leq(1, 0, n-1, r+1, n-1, b);
					ans += v[c] - v[l];
					r = c;
					dir = 1 - dir;
				}
				else{
					int a = v[r];
					int b = nxt[r];
					//bsta on segtree 2, first one (invert) > b, on [0, l - 1].
					int c = first_greater(1, 0, n-1, 0, l-1, b);
					ans += v[r] - v[c];
					l = c;
					dir = 1 - dir;
				}
			}
		}
		
		out(ans);
	}
}

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