Submission #857407


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;
		for (int i=19;i>=0;i--) {
			if (leap[i][cur]<=b) {
				cur=leap[i][cur];
				sum|=1<<i;
			}
		}
		if (cur<b) sum++;
		/*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 1013 Byte
Status WA
Exec Time 148 ms
Memory 9088 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 0 / 200 0 / 500
Status
AC × 1
AC × 1
WA × 13
AC × 1
WA × 26
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 WA 4 ms 384 KB
subtask1_02.txt WA 4 ms 384 KB
subtask1_03.txt WA 5 ms 384 KB
subtask1_04.txt WA 5 ms 384 KB
subtask1_05.txt WA 7 ms 384 KB
subtask1_06.txt WA 5 ms 384 KB
subtask1_07.txt WA 5 ms 384 KB
subtask1_08.txt WA 5 ms 384 KB
subtask1_09.txt WA 5 ms 384 KB
subtask1_10.txt WA 5 ms 384 KB
subtask1_11.txt WA 5 ms 384 KB
subtask1_12.txt WA 5 ms 384 KB
subtask1_13.txt WA 5 ms 384 KB
subtask2_01.txt WA 127 ms 8960 KB
subtask2_02.txt WA 148 ms 9088 KB
subtask2_03.txt WA 125 ms 8832 KB
subtask2_04.txt WA 63 ms 5888 KB
subtask2_05.txt WA 82 ms 6016 KB
subtask2_06.txt WA 100 ms 8704 KB
subtask2_07.txt WA 140 ms 8960 KB
subtask2_08.txt WA 138 ms 8960 KB
subtask2_09.txt WA 134 ms 8960 KB
subtask2_10.txt WA 135 ms 8960 KB
subtask2_11.txt WA 132 ms 8448 KB
subtask2_12.txt WA 83 ms 9088 KB
subtask2_13.txt WA 97 ms 8704 KB