oj.uz

Submission #973307

# Submission time Handle Problem Language Result Execution time Memory
973307 2024-05-01T17:53:07 Z happy_node Bitaro's travel (JOI23_travel) C++17
30 / 100
 982 ms 22268 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 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]=-2e9;
	X[N+1]=2e9;
 
	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++) { 

		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.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);	
				}
			}
		}
		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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 7 ms 6644 KB Output is correct
3 Correct 7 ms 6492 KB Output is correct
4 Correct 6 ms 6492 KB Output is correct
5 Correct 5 ms 6636 KB Output is correct
6 Correct 5 ms 6492 KB Output is correct
7 Correct 5 ms 6492 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Incorrect 2 ms 6492 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 7 ms 6644 KB Output is correct
3 Correct 7 ms 6492 KB Output is correct
4 Correct 6 ms 6492 KB Output is correct
5 Correct 5 ms 6636 KB Output is correct
6 Correct 5 ms 6492 KB Output is correct
7 Correct 5 ms 6492 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Incorrect 2 ms 6492 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4564 KB Output is correct
5 Correct 1 ms 4440 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 903 ms 20736 KB Output is correct
8 Correct 888 ms 20604 KB Output is correct
9 Correct 913 ms 20596 KB Output is correct
10 Correct 899 ms 20596 KB Output is correct
11 Correct 887 ms 20596 KB Output is correct
12 Correct 901 ms 20596 KB Output is correct
13 Correct 30 ms 8532 KB Output is correct
14 Correct 22 ms 5724 KB Output is correct
15 Correct 943 ms 21768 KB Output is correct
16 Correct 944 ms 22268 KB Output is correct
17 Correct 982 ms 21804 KB Output is correct
18 Correct 32 ms 8540 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 7 ms 6644 KB Output is correct
3 Correct 7 ms 6492 KB Output is correct
4 Correct 6 ms 6492 KB Output is correct
5 Correct 5 ms 6636 KB Output is correct
6 Correct 5 ms 6492 KB Output is correct
7 Correct 5 ms 6492 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Incorrect 2 ms 6492 KB Output isn't correct
13 Halted 0 ms 0 KB -