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

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 2016-08-28 23:03:42+0900 E - Tak and Hotels Whalanator C++14 (GCC 5.4.1) 0 1013 Byte WA 148 ms 9088 KB

#### Judge Result

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
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