Submission #972873

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

travel

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MX=2e5+5;
int N,Q;
int X[MX];

ll val[MX];

struct segtree {
    	int 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]);
     	}
 
     	int query(int v, int l, int r, int ql, int qr) {
           	if(ql > r || qr < l) return 2e9;
           	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 {
      	int 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 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;

	for(int i=1;i<=N+1;i++) st.update(1,1,N,i,2*X[i+1]-X[i]);
	for(int i=1;i<=N+1;i++) tt.update(1,1,N,i,2*X[i]-X[i-1]);

	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;
		}

		while(true) {
			if(i<j) {
				int l=j,r=N,res=N;
				while(l<=r) {
					int mid=(l+r)/2;
					if(st.query(1,1,N,j+1,mid)<=X[i-1]) {
						res=mid,r=mid-1;
 					} else {
 						l=mid+1;
 					}
				}

				val[p]+=X[res]-X[j];
				val[p]+=X[res]-X[i];

				j=res;
				swap(i,j);

			} else { // j < i
				int l=1,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,l=mid+1;
 					} else {
 						r=mid-1;
 					}
				}

				val[p]+=X[j]-X[res];
				val[p]+=X[i]-X[res];
				j=res;
				swap(i,j);
			}

			if((i==1 && j==N) || (i==N && j==1)) break;
		}

		val[p]-=X[N]-X[1];

		i=p;
	}

	cin>>Q;
	for(int i=1;i<=Q;i++) {
		int x;
		cin>>x;
		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