Submission #1230484


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;

#define for_(i,a,b) for(int i=(a);i<(b);++i)

void solve(int N, const vector< int >& x, int L) {
	vector< vector< int > > par_L(N, vector< int >(25, -1));
	vector< vector< int > > par_R(N, vector< int >(25, -1));
	
	for_(i,0,N) {
		// par L
		int lb = -1, ub = i-1;
		while (ub - lb > 1) {
			int med = (ub + lb) / 2;
			if (x[i] - x[med] > L) lb = med;
			else ub = med;
		}
		par_L[i][0] = ub;
		
		// par R
		lb = i + 1; ub = N;
		while (ub - lb > 1) {
			int med = (ub + lb) / 2;
			if (x[med] - x[i] > L) ub = med;
			else lb = med;
		}
		par_R[i][0] = (lb == N ? -1 : lb);
	}
	
	for_(k,1,25) for_(i,0,N) {
		int pL = par_L[i][k - 1];
		if (pL != -1) par_L[i][k] = par_L[pL][k - 1];
		int pR = par_R[i][k - 1];
		if (pR != -1) par_R[i][k] = par_R[pR][k - 1];
	}
	
	int Q;
	cin >> Q;
	
	for_(q,0,Q) {
		int a, b;
		cin >> a >> b;
		--a; --b;
		
		if (a < b) {
			int day = 0, cur = a, k = 24;
			while (cur < b) {
				while (k > 0 && (par_R[cur][k] == -1 || par_R[cur][k] > b)) --k;
				day += (1 << k);
				cur = par_R[cur][k];
			}
			printf("%d\n", day);
		} else {
			int day = 0, cur = a, k = 24;
			while (cur > b) {
				while (k > 0 && (par_L[cur][k] == -1 || par_L[cur][k] < b)) --k;
				day += (1 << k);
				cur = par_L[cur][k];
			}
			printf("%d\n", day);			
		}
	}
}

int main() {
	int N;
	cin >> N;
	
	vector< int > x(N);
	for_(i,0,N) cin >> x[i];
	
	int L;
	cin >> L;
	
	solve(N, x, L);
}

Submission Info

Submission Time
Task E - Tak and Hotels
User tsukasa_diary
Language C++14 (GCC 5.4.1)
Score 700
Code Size 1528 Byte
Status AC
Exec Time 396 ms
Memory 29312 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 200 / 200 500 / 500
Status
AC × 1
AC × 14
AC × 27
Set Name Test Cases
Sample example_01.txt
Subtask1 example_01.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt
All example_01.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt
Case Name Status Exec Time Memory
example_01.txt AC 1 ms 256 KB
subtask1_01.txt AC 1 ms 256 KB
subtask1_02.txt AC 1 ms 256 KB
subtask1_03.txt AC 4 ms 512 KB
subtask1_04.txt AC 4 ms 512 KB
subtask1_05.txt AC 4 ms 512 KB
subtask1_06.txt AC 3 ms 384 KB
subtask1_07.txt AC 3 ms 384 KB
subtask1_08.txt AC 4 ms 512 KB
subtask1_09.txt AC 4 ms 512 KB
subtask1_10.txt AC 4 ms 512 KB
subtask1_11.txt AC 4 ms 512 KB
subtask1_12.txt AC 4 ms 512 KB
subtask1_13.txt AC 4 ms 512 KB
subtask2_01.txt AC 368 ms 27648 KB
subtask2_02.txt AC 396 ms 27776 KB
subtask2_03.txt AC 388 ms 27520 KB
subtask2_04.txt AC 208 ms 18048 KB
subtask2_05.txt AC 235 ms 18176 KB
subtask2_06.txt AC 331 ms 29312 KB
subtask2_07.txt AC 365 ms 27648 KB
subtask2_08.txt AC 393 ms 27776 KB
subtask2_09.txt AC 385 ms 27776 KB
subtask2_10.txt AC 388 ms 27776 KB
subtask2_11.txt AC 379 ms 25600 KB
subtask2_12.txt AC 322 ms 27776 KB
subtask2_13.txt AC 325 ms 27392 KB