Submission #973291

#	Time	Username	Problem	Language	Result	Execution time	Memory
973291		happy_node	Bitaro's travel (JOI23_travel)	C++17	0 / 100	9 ms	8912 KiB

travel

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
const int MX=2e5+5;
int N,Q;
ll X[MX];
 
ll val[MX];
 
struct segtree {
    	ll t[4 * MX];
 
     	void update(int v, int l, int r, int pos, int val) {
           	if(l > pos || r < pos) return;
           	if(l == r) {
                 	t[v] = val;
                 	return;
           	}
           	int mid = (l + r) >> 1;
           	update(v * 2 + 0, l, mid + 0, pos, val);
           	update(v * 2 + 1, mid + 1, r, pos, val);
           	t[v] = min(t[v * 2 + 0], t[v * 2 + 1]);
     	}
 
     	ll query(int v, int l, int r, int ql, int qr) {
           	if(ql > r || qr < l) return 2e18;
           	if(ql <= l && qr >= r) return t[v];
           	int mid = (l + r) >> 1;
           	return min(query(v * 2 + 0, l, mid + 0, ql, qr), query(v * 2 + 1, mid + 1, r, ql, qr));
      	}
} st;
 
struct ST {
      	ll t[4 * MX];
 
     	void update(int v, int l, int r, int pos, int val) {
           	if(l > pos || r < pos) return;
           	if(l == r) {
                 	t[v] = val;
                 	return;
            	}
            	int mid = (l + r) >> 1;
            	update(v * 2 + 0, l, mid + 0, pos, val);
            	update(v * 2 + 1, mid + 1, r, pos, val);
            	t[v] = max(t[v * 2 + 0], t[v * 2 + 1]);
      	}
 
      	int query(int v, int l, int r, int ql, int qr) {
           	if(ql > r || qr < l) return 0;
                if(ql <= l && qr >= r) return t[v];
           	int mid = (l + r) >> 1;
           	return max(query(v * 2 + 0, l, mid + 0, ql, qr), query(v * 2 + 1, mid + 1, r, ql, qr));
      	}
} tt;
 
int S[MX];
 
int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);
 
	cin>>N;
 
	for(int i=1;i<=N;i++) cin>>X[i];
	X[0]=-1e9;
	X[N+1]=1e9;
 
	cin>>Q;
	for(int i=1;i<=Q;i++) cin>>S[i];
 
	for(int i=1;i<N;i++) st.update(1,1,N,i,2*X[i]-X[i+1]); // go right
	st.update(1,1,N,N,-2e9);
	for(int i=2;i<=N;i++) tt.update(1,1,N,i,2*X[i]-X[i-1]); // go left
	tt.update(1,1,N,1,2e9);
 
	for(int i=1;i<=N;i++) { 
		int p=i;
		int j=i;
 
		if(X[i]-X[i-1]<=X[i+1]-X[i]) {
			val[p]+=X[i]-X[i-1];
			j-=1;
		} else {
			val[p]+=X[i+1]-X[i];
			j+=1;
		}
 
		int its=0;
		while(!(min(i,j)==1 && max(i,j)==N)) {
			if(i<j) {
				int l=j,r=N-1,res=-1;
				while(l<=r) {
					int mid=(l+r)/2;
					if(st.query(1,1,N,j,mid)>X[i-1]) {
						res=mid,l=mid+1;
 					} else {
 						r=mid-1;
 					}
				}
 
				if(res==-1) {
					val[p]+=X[j]-X[i];
					swap(i,j);
				} else {
					res+=1;
					val[p]+=X[res]-X[j];
					val[p]+=X[res]-X[i];
					j=res;
					swap(i,j);
				}
 
			} else { // j < i
				int l=2,r=j,res=-1;
				while(l<=r) {
					int mid=(l+r)/2;
					if(tt.query(1,1,N,mid,j)<=X[i+1]) {
						res=mid,r=mid-1;
 					} else {
 						l=mid+1;
 					}
				}
 
				if(res==-1) {
					val[p]+=X[i]-X[j];
					swap(i,j);
				} else {
					res-=1;
					val[p]+=X[j]-X[res];
					val[p]+=X[i]-X[res];
					j=res;
					swap(i,j);	
				}
			}
			its++;
			assert(its<=40);
		}
		val[p]-=X[N]-X[1];
		i=p;
	}
 
	for(int i=1;i<=Q;i++) {
		int x=S[i];
		auto it=lower_bound(X+1,X+N+1,x)-X;
		if(X[it]-x<x-X[it-1]) {
			cout<<val[it]+X[it]-x<<'\n';
		} else {
			cout<<val[it-1]+x-X[it-1]<<'\n';
		}
	}
}

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