Submission #936290


Source Code Expand

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

#define FOR(i,l,r) for(int i = (l);i < (r);i++)
#define ALL(x) (x).begin(),(x).end()
template<typename T> void chmax(T& a,const T& b){if(a < b) a = b;}
template<typename T> void chmin(T& a,const T& b){if(b < a) a = b;}
typedef long long ll;

int N,L,Q;
int nx [18] [100000];

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);

	cin >> N;
	vector<int> X(N);
	FOR(i,0,N){
		cin >> X [i];
	}
	cin >> L >> Q;

	FOR(i,0,N){
		nx [0] [i] = upper_bound(ALL(X),X [i] + L) - X.begin() - 1;
	}
	FOR(i,1,18){
		FOR(j,0,N){
			nx [i] [j] = nx [i - 1] [nx [i - 1] [j]];
		}
	}

	FOR(i,0,Q){
		int A,B;
		cin >> A >> B;
		A--,B--;
		if(A > B) swap(A,B);
		int ans = 0,cur = A;
		for(int i = 17;i >= 0;i--){
			if(nx [i] [cur] < B){
				cur = nx [i] [cur];
				ans += 1 << i;
			}
		}
		if(cur < B) ans++;
		cout << ans << endl;
	}

	return 0;
}

Submission Info

Submission Time
Task E - Tak and Hotels
User gigime
Language C++14 (GCC 5.4.1)
Score 700
Code Size 935 Byte
Status AC
Exec Time 501 ms
Memory 8320 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 3 ms 384 KB
subtask1_01.txt AC 3 ms 384 KB
subtask1_02.txt AC 3 ms 384 KB
subtask1_03.txt AC 7 ms 384 KB
subtask1_04.txt AC 7 ms 384 KB
subtask1_05.txt AC 7 ms 384 KB
subtask1_06.txt AC 5 ms 384 KB
subtask1_07.txt AC 5 ms 384 KB
subtask1_08.txt AC 7 ms 384 KB
subtask1_09.txt AC 7 ms 384 KB
subtask1_10.txt AC 7 ms 384 KB
subtask1_11.txt AC 7 ms 384 KB
subtask1_12.txt AC 7 ms 384 KB
subtask1_13.txt AC 7 ms 384 KB
subtask2_01.txt AC 490 ms 8192 KB
subtask2_02.txt AC 501 ms 8192 KB
subtask2_03.txt AC 485 ms 8064 KB
subtask2_04.txt AC 308 ms 5376 KB
subtask2_05.txt AC 323 ms 5504 KB
subtask2_06.txt AC 473 ms 7936 KB
subtask2_07.txt AC 497 ms 8192 KB
subtask2_08.txt AC 496 ms 8320 KB
subtask2_09.txt AC 497 ms 8192 KB
subtask2_10.txt AC 498 ms 8192 KB
subtask2_11.txt AC 492 ms 7808 KB
subtask2_12.txt AC 465 ms 8320 KB
subtask2_13.txt AC 475 ms 7936 KB