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

Submission #1230484

Source Code Expand

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

#define for_(i,a,b) for(int i=(a);i<(b);++i)

void solve(int N, const vector< int >& x, int L) {
vector< vector< int > > par_L(N, vector< int >(25, -1));
vector< vector< int > > par_R(N, vector< int >(25, -1));

for_(i,0,N) {
// par L
int lb = -1, ub = i-1;
while (ub - lb > 1) {
int med = (ub + lb) / 2;
if (x[i] - x[med] > L) lb = med;
else ub = med;
}
par_L[i][0] = ub;

// par R
lb = i + 1; ub = N;
while (ub - lb > 1) {
int med = (ub + lb) / 2;
if (x[med] - x[i] > L) ub = med;
else lb = med;
}
par_R[i][0] = (lb == N ? -1 : lb);
}

for_(k,1,25) for_(i,0,N) {
int pL = par_L[i][k - 1];
if (pL != -1) par_L[i][k] = par_L[pL][k - 1];
int pR = par_R[i][k - 1];
if (pR != -1) par_R[i][k] = par_R[pR][k - 1];
}

int Q;
cin >> Q;

for_(q,0,Q) {
int a, b;
cin >> a >> b;
--a; --b;

if (a < b) {
int day = 0, cur = a, k = 24;
while (cur < b) {
while (k > 0 && (par_R[cur][k] == -1 || par_R[cur][k] > b)) --k;
day += (1 << k);
cur = par_R[cur][k];
}
printf("%d\n", day);
} else {
int day = 0, cur = a, k = 24;
while (cur > b) {
while (k > 0 && (par_L[cur][k] == -1 || par_L[cur][k] < b)) --k;
day += (1 << k);
cur = par_L[cur][k];
}
printf("%d\n", day);
}
}
}

int main() {
int N;
cin >> N;

vector< int > x(N);
for_(i,0,N) cin >> x[i];

int L;
cin >> L;

solve(N, x, L);
}```

#### Submission Info

Submission Time 2017-04-20 20:08:57+0900 E - Tak and Hotels tsukasa_diary C++14 (GCC 5.4.1) 700 1528 Byte AC 396 ms 29312 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 1 ms 256 KB
subtask1_01.txt AC 1 ms 256 KB
subtask1_02.txt AC 1 ms 256 KB
subtask1_03.txt AC 4 ms 512 KB
subtask1_04.txt AC 4 ms 512 KB
subtask1_05.txt AC 4 ms 512 KB
subtask1_06.txt AC 3 ms 384 KB
subtask1_07.txt AC 3 ms 384 KB
subtask1_08.txt AC 4 ms 512 KB
subtask1_09.txt AC 4 ms 512 KB
subtask1_10.txt AC 4 ms 512 KB
subtask1_11.txt AC 4 ms 512 KB
subtask1_12.txt AC 4 ms 512 KB
subtask1_13.txt AC 4 ms 512 KB
subtask2_01.txt AC 368 ms 27648 KB
subtask2_02.txt AC 396 ms 27776 KB
subtask2_03.txt AC 388 ms 27520 KB
subtask2_04.txt AC 208 ms 18048 KB
subtask2_05.txt AC 235 ms 18176 KB
subtask2_06.txt AC 331 ms 29312 KB
subtask2_07.txt AC 365 ms 27648 KB
subtask2_08.txt AC 393 ms 27776 KB
subtask2_09.txt AC 385 ms 27776 KB
subtask2_10.txt AC 388 ms 27776 KB
subtask2_11.txt AC 379 ms 25600 KB
subtask2_12.txt AC 322 ms 27776 KB
subtask2_13.txt AC 325 ms 27392 KB