Contest Duration: - (local time) (100 minutes) Back to Home

Submission #857430

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;
}
}
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 2016-08-28 23:07:18+0900 E - Tak and Hotels Whalanator C++14 (GCC 5.4.1) 700 1001 Byte AC 139 ms 9088 KB

#### Judge Result

Score / Max Score 0 / 0 200 / 200 500 / 500
Status
 AC × 1
 AC × 14
 AC × 27
Set Name Test Cases
Sample example_01.txt
Case Name Status Exec Time Memory
example_01.txt AC 4 ms 384 KB
subtask1_01.txt AC 4 ms 384 KB
subtask1_02.txt AC 4 ms 384 KB
subtask1_03.txt AC 5 ms 384 KB
subtask1_04.txt AC 5 ms 384 KB
subtask1_05.txt AC 5 ms 384 KB
subtask1_06.txt AC 5 ms 384 KB
subtask1_07.txt AC 5 ms 384 KB
subtask1_08.txt AC 5 ms 384 KB
subtask1_09.txt AC 5 ms 384 KB
subtask1_10.txt AC 5 ms 384 KB
subtask1_11.txt AC 5 ms 384 KB
subtask1_12.txt AC 7 ms 384 KB
subtask1_13.txt AC 7 ms 384 KB
subtask2_01.txt AC 136 ms 8960 KB
subtask2_02.txt AC 136 ms 9088 KB
subtask2_03.txt AC 127 ms 8832 KB
subtask2_04.txt AC 62 ms 5888 KB
subtask2_05.txt AC 84 ms 6016 KB
subtask2_06.txt AC 105 ms 8704 KB
subtask2_07.txt AC 136 ms 8960 KB
subtask2_08.txt AC 134 ms 8960 KB
subtask2_09.txt AC 137 ms 8960 KB
subtask2_10.txt AC 139 ms 8960 KB
subtask2_11.txt AC 132 ms 8448 KB
subtask2_12.txt AC 80 ms 9088 KB
subtask2_13.txt AC 97 ms 8704 KB