Submission #857318


Source Code Expand

Copy
#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> ii;
typedef pair<ll,ll> pll;

int leap[20][100000];
int xs[100000],N,L,Q;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;
	for (int i=0;i<N;i++) cin >> xs[i];
	int cr=N-1;
	cin >> L;
	for (int i=N-1;i>=0;i--) {
		while (xs[cr]-xs[i]>L) cr--;
		leap[0][i]=cr;
	}

	for (int i=1;i<20;i++) for (int j=0;j<N;j++) leap[i][j]=leap[i-1][leap[i-1][j]];

	cin >> Q;
	while (Q--) {
		int a,b;
		cin >> a >> b;
		a--;b--;
		if (a>b) swap(a,b);
		int sum=0,cur=a;
		while(cur!=b) {
			for (int i=0;;i++) {
				if (leap[i+1][cur]>b) {
					cur=leap[i][cur];
					sum+=1<<i;
					break;
				}
			}
		}

		cout << sum << '\n';
	}

}

Submission Info

Submission Time
Task E - Tak and Hotels
User Whalanator
Language C++14 (GCC 5.4.1)
Score 0
Code Size 882 Byte
Status TLE
Exec Time 3157 ms
Memory 8704 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 0 / 200 0 / 500
Status
AC × 1
AC × 1
TLE × 10
RE × 3
AC × 1
TLE × 22
RE × 4
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 4 ms 384 KB
subtask1_01.txt TLE 3157 ms 384 KB
subtask1_02.txt RE 193 ms 384 KB
subtask1_03.txt TLE 3153 ms 384 KB
subtask1_04.txt RE 190 ms 384 KB
subtask1_05.txt TLE 3153 ms 384 KB
subtask1_06.txt RE 190 ms 384 KB
subtask1_07.txt TLE 3157 ms 384 KB
subtask1_08.txt TLE 3153 ms 384 KB
subtask1_09.txt TLE 3153 ms 384 KB
subtask1_10.txt TLE 3153 ms 384 KB
subtask1_11.txt TLE 3157 ms 384 KB
subtask1_12.txt TLE 3157 ms 384 KB
subtask1_13.txt TLE 3153 ms 384 KB
subtask2_01.txt TLE 3154 ms 8448 KB
subtask2_02.txt RE 273 ms 8704 KB
subtask2_03.txt TLE 3154 ms 8448 KB
subtask2_04.txt TLE 3154 ms 5760 KB
subtask2_05.txt TLE 3154 ms 5760 KB
subtask2_06.txt TLE 3156 ms 8448 KB
subtask2_07.txt TLE 3154 ms 8448 KB
subtask2_08.txt TLE 3154 ms 8448 KB
subtask2_09.txt TLE 3154 ms 8448 KB
subtask2_10.txt TLE 3154 ms 8448 KB
subtask2_11.txt TLE 3157 ms 7936 KB
subtask2_12.txt TLE 3154 ms 8448 KB
subtask2_13.txt TLE 3154 ms 8448 KB