oj.uz

Submission #973282

# Submission time Handle Problem Language Result Execution time Memory
973282 2024-05-01T17:32:19 Z happy_node Bitaro's travel (JOI23_travel) C++17
0 / 100
 3000 ms 4444 KB 
#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 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;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,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);
					continue;
				}

				res+=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,r=mid-1;
 					} else {
 						l=mid+1;
 					}
				}

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

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

	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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Execution timed out 3088 ms 4444 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Execution timed out 3088 ms 4444 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Execution timed out 3044 ms 4444 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Execution timed out 3088 ms 4444 KB Time limit exceeded
3 Halted 0 ms 0 KB -