Submission #973311

#	Time	Username	Problem	Language	Result	Execution time	Memory
973311		happy_node	Bitaro's travel (JOI23_travel)	C++17	100 / 100	349 ms	74772 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], LOG[MX];
 
struct ST1 {
    	ll st[MX][20];

    	int que(int l, int r) {
    		int lg=LOG[r-l+1];
    		return min(st[l][lg],st[r-(1<<lg)+1][lg]);
    	}

    	void prep() {
    		for(int i=1;i<N;i++) st[i][0]=2*X[i]-X[i+1];
    		st[N][0]=-2e9;

    		for(int k=1;k<20;k++) {
    			for(int i=1;i+(1<<k)<=N;i++) {
    				st[i][k]=min(st[i][k-1],st[i+(1<<(k-1))][k-1]);
    			}
    		}
    	}	
} st;
 
struct ST2 {
      	ll st[MX][20];

      	int que(int l, int r) {
    		int lg=LOG[r-l+1];
    		return max(st[l][lg],st[r-(1<<lg)+1][lg]);
    	}

    	void prep() {
    		for(int i=2;i<=N;i++) st[i][0]=2*X[i]-X[i-1];
    		st[1][0]=2e9;

    		for(int k=1;k<20;k++) {
    			for(int i=1;i+(1<<k)<=N;i++) {
    				st[i][k]=max(st[i][k-1],st[i+(1<<(k-1))][k-1]);
    			}
    		}
    	}	
} tt;
 
int S[MX];
 
int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);

	LOG[1]=0;
	for(int i=2;i<MX;i++) LOG[i]=LOG[i/2]+1;
 
	cin>>N;
 
	for(int i=1;i<=N;i++) cin>>X[i];

	X[0]=-2e9;
	X[N+1]=2e9;
 
	cin>>Q;
	for(int i=1;i<=Q;i++) cin>>S[i];
 
	st.prep();
	tt.prep();
 
	for(int i=1;i<=N;i++) { 
		if(N==1) break;

		int p=i;
		int j=i;

		if(i==1) {
			val[p]+=X[i+1]-X[i];
			j+=1;
		} else if(i==N) {
			val[p]+=X[i]-X[i-1];
			j-=1;
		} else {
			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;
			}
		}

		assert(min(i,j)>=1 && max(i,j)<=N);
 
		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.que(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];
					j=res;
				}
 
			} else { // j < i
				int l=2,r=j,res=-1;
				while(l<=r) {
					int mid=(l+r)/2;
					if(tt.que(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];
					j=res;
				}
			}
		}

		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: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 55 / 55