oj.uz

Submission #954240

# Submission time Handle Problem Language Result Execution time Memory
954240 2024-03-27T13:30:30 Z LCJLY Bitaro's travel (JOI23_travel) C++14
0 / 100
 2 ms 968 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
typedef pair<pii,pii>pi2;
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
 
struct SparseTable {
    vector<vector<int> > ST;
    int N, K;
    SparseTable(int _N, int a[]): N(_N) {
        K = MSB(N);
        ST.resize(K);
        ST[0] = vector<int>(a, a+N);
        for (int k = 1; k < K; ++k) 
            for (int i = 0; i+(1<<k) <= N; ++i) 
                ST[k].push_back( min(ST[k-1][i], ST[k-1][i+(1<<(k-1))]) ); 
    }
 
    inline int MSB(unsigned int x) { return 32-__builtin_clz(x); }
    
    int query(int x, int y) {
        int k = MSB(y-x+1) - 1;
        return min(ST[k][x], ST[k][y-(1<<k)+1]);            
    }
};
 
struct SparseTable2 {
    vector<vector<int> > ST;
    int N, K;
    SparseTable2(int _N, int a[]): N(_N) {
        K = MSB(N);
        ST.resize(K);
        ST[0] = vector<int>(a, a+N);
        for (int k = 1; k < K; ++k) 
            for (int i = 0; i+(1<<k) <= N; ++i) 
                ST[k].push_back( max(ST[k-1][i], ST[k-1][i+(1<<(k-1))]) ); 
    }
 
    inline int MSB(unsigned int x) { return 32-__builtin_clz(x); }
    
    int query(int x, int y) {
        int k = MSB(y-x+1) - 1;
        return max(ST[k][x], ST[k][y-(1<<k)+1]);            
    }
};
 
 
void solve(){
	int n;
	cin >> n;
	int arr[n+5];
	for(int x=1;x<=n;x++){
		cin >> arr[x];
	}
	arr[0]=-1e17;
	arr[n+1]=1e17;
	
	int r[n+5];
	int l[n+5];
	l[0]=1e15;
	r[n+1]=-1e15;
	for(int x=1;x<=n;x++){
		l[x]=2*arr[x]-arr[x-1];
		r[x]=2*arr[x]-arr[x+1];
	}
	
	SparseTable2 st(n+2,l);
	SparseTable st2(n+2,r);
	
	int q;
	cin >> q;
	
	for(int x=0;x<q;x++){
		int index;
		cin >> index;
		
		int cur=0;
		int hold=lower_bound(arr,arr+n+2,index)-arr;
		if(index-arr[hold-1]<=arr[hold]-index) cur=hold-1;
		else cur=hold;
		
		int counter=abs(index-arr[cur]);
		
		bool amos=true;
		
		if(arr[cur]-arr[cur-1]<=arr[cur+1]-arr[cur]) amos=false;
		
		int left=cur;
		int right=cur;
		
		while(left>1&&right<n){
			if(amos){
				//venture right
				int target=arr[left-1];
				//modify
				
				//for(int y=cur+1;y<=n;y++){
					//right=y;
					//if(r[y]<=target) break;
				//}
				
				int lft=cur;
				int rgt=n;
				int mid;
				int best=rgt;
				
				while(lft<=rgt){
					//show2(lft,lft,rgt,rgt);
					mid=(lft+rgt)/2;
					if(st2.query(cur+1,mid)<=target){
						best=mid;
						rgt=mid-1;
					}
					else lft=mid+1;
				}
				
				right=best;
				
				
				//modify
				counter+=abs(arr[left-1]-arr[right]);
				counter+=abs(arr[right]-arr[cur]);
				cur=left-1;
				left--;
				amos=false;
			}
			else{
				//venture left
				int target=arr[right+1];
				
				//modify
				//for(int y=cur-1;y>=1;y--){
					//left=y;
					//if(l[y]>target) break;
				//}
				
				int lft=1;
				int rgt=cur;
				int mid;
				int best=lft;
				
				while(lft<=rgt){
					//show2(lft,lft,rgt,rgt);
					mid=(lft+rgt)/2;
					if(st.query(mid,cur-1)>target){
						best=mid;
						lft=mid+1;
					}
					else rgt=mid-1;
				}
				
				left=best;
				
				
				
				//modify
				counter+=abs(arr[left]-arr[right+1]);
				counter+=abs(arr[left]-arr[cur]);
				cur=right+1;
				right++;
				amos=true;
			}
		}
		if(left!=1){
			counter+=abs(arr[cur]-arr[1]);
		}	
		if(right!=n){
			counter+=abs(arr[cur]-arr[n]);
		}
		cout << counter << "\n";
	}
	
}	
 
/*
10
1 2 3 4 5 6 7 8 9 10
1
2
*/
 
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	//cin >> t;
	while(t--){
		solve();
	}
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 2 ms 968 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 364 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 460 KB Output is correct
14 Correct 1 ms 748 KB Output is correct
15 Correct 1 ms 724 KB Output is correct
16 Incorrect 1 ms 860 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 2 ms 968 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 364 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 460 KB Output is correct
14 Correct 1 ms 748 KB Output is correct
15 Correct 1 ms 724 KB Output is correct
16 Incorrect 1 ms 860 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 460 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 2 ms 968 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 364 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 460 KB Output is correct
14 Correct 1 ms 748 KB Output is correct
15 Correct 1 ms 724 KB Output is correct
16 Incorrect 1 ms 860 KB Output isn't correct
17 Halted 0 ms 0 KB -