oj.uz

Submission #973308

# Submission time Handle Problem Language Result Execution time Memory
973308 2024-05-01T17:55:05 Z happy_node Bitaro's travel (JOI23_travel) C++17
35 / 100
 3000 ms 18964 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];
					j=res;
				}
 
			} 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];
					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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 8 ms 6492 KB Output is correct
3 Correct 12 ms 6748 KB Output is correct
4 Correct 6 ms 6488 KB Output is correct
5 Correct 6 ms 6492 KB Output is correct
6 Correct 5 ms 6640 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 4440 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 5 ms 6492 KB Output is correct
15 Correct 5 ms 6492 KB Output is correct
16 Correct 5 ms 6492 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 8 ms 6492 KB Output is correct
3 Correct 12 ms 6748 KB Output is correct
4 Correct 6 ms 6488 KB Output is correct
5 Correct 6 ms 6492 KB Output is correct
6 Correct 5 ms 6640 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 4440 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 5 ms 6492 KB Output is correct
15 Correct 5 ms 6492 KB Output is correct
16 Correct 5 ms 6492 KB Output is correct
17 Correct 2135 ms 18584 KB Output is correct
18 Correct 2149 ms 18740 KB Output is correct
19 Correct 2199 ms 18512 KB Output is correct
20 Correct 2109 ms 18800 KB Output is correct
21 Correct 2196 ms 18964 KB Output is correct
22 Correct 2171 ms 18560 KB Output is correct
23 Correct 2108 ms 18600 KB Output is correct
24 Correct 1110 ms 18808 KB Output is correct
25 Correct 1101 ms 18556 KB Output is correct
26 Correct 1110 ms 18552 KB Output is correct
27 Correct 1130 ms 18512 KB Output is correct
28 Correct 1097 ms 18560 KB Output is correct
29 Execution timed out 3045 ms 18236 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 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 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 897 ms 18060 KB Output is correct
8 Correct 914 ms 18060 KB Output is correct
9 Correct 907 ms 18060 KB Output is correct
10 Correct 889 ms 18256 KB Output is correct
11 Correct 926 ms 18260 KB Output is correct
12 Correct 895 ms 18344 KB Output is correct
13 Correct 29 ms 6480 KB Output is correct
14 Correct 23 ms 5212 KB Output is correct
15 Correct 968 ms 18532 KB Output is correct
16 Correct 975 ms 18848 KB Output is correct
17 Correct 966 ms 18572 KB Output is correct
18 Correct 33 ms 6680 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 8 ms 6492 KB Output is correct
3 Correct 12 ms 6748 KB Output is correct
4 Correct 6 ms 6488 KB Output is correct
5 Correct 6 ms 6492 KB Output is correct
6 Correct 5 ms 6640 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 4440 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 5 ms 6492 KB Output is correct
15 Correct 5 ms 6492 KB Output is correct
16 Correct 5 ms 6492 KB Output is correct
17 Correct 2135 ms 18584 KB Output is correct
18 Correct 2149 ms 18740 KB Output is correct
19 Correct 2199 ms 18512 KB Output is correct
20 Correct 2109 ms 18800 KB Output is correct
21 Correct 2196 ms 18964 KB Output is correct
22 Correct 2171 ms 18560 KB Output is correct
23 Correct 2108 ms 18600 KB Output is correct
24 Correct 1110 ms 18808 KB Output is correct
25 Correct 1101 ms 18556 KB Output is correct
26 Correct 1110 ms 18552 KB Output is correct
27 Correct 1130 ms 18512 KB Output is correct
28 Correct 1097 ms 18560 KB Output is correct
29 Execution timed out 3045 ms 18236 KB Time limit exceeded
30 Halted 0 ms 0 KB -