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

Submission #856627

Source Code Expand

Copy
```#include <iostream>
#include <iomanip>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <cstdio>
#include <cstring>
using namespace std;

int main()
{
int n;
scanf("%d", &n);

vector<int> xs(n);
for (auto &x: xs) scanf("%d", &x);

int l, q;
scanf("%d%d", &l, &q);

vector<pair<int, int>> qs(q);
for (auto &q: qs) scanf("%d%d", &q.first, &q.second), q.first--, q.second--;

vector<vector<int>> skip(20, vector<int>(n));

for (int i = 0; i < 20; i++) {
for (int j = 0; j < n; j++) {
if (i == 0) {
if (j == n - 1) skip[i][j] = n;
else skip[i][j] = prev(upper_bound(xs.begin(), xs.end(), xs[j] + l)) - xs.begin();
} else {
skip[i][j] = skip[i - 1][j];
if (skip[i][j] < n) skip[i][j] = skip[i - 1][skip[i][j]];
}
}

// if (i == 0) {
//     for (int j = 0; j < n; j++) {
//         cerr << "* " << j << ": " << skip[i][j] << endl;
//     }
//     return 0;
// }
}

for (auto &q: qs) {
int ans = 0, cur = q.first, goal = q.second;
if (cur > goal) swap(cur, goal);

while (cur < goal) {
// cerr << "* " << cur << endl;
int longest = 0, next = cur;
for (int i = 0; i < 20; i++) {
if (skip[i][cur] > goal) break;
else {
longest = 1 << i;
next = skip[i][cur];
}
}
cur = next;
ans += longest;
}

cout << ans << endl;
}

return 0;
}```

#### Submission Info

Submission Time 2016-08-28 22:13:38+0900 E - Tak and Hotels tanakh C++14 (GCC 5.4.1) 0 1754 Byte TLE 3158 ms 9848 KB

#### Compile Error

```./Main.cpp: In function ‘int main()’:
./Main.cpp:15:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
^
./Main.cpp:18:38: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
for (auto &x: xs) scanf("%d", &x);
^
./Main.cpp:21:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &l, &q);
^
./Main.cpp:24:80: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
for (auto &q: qs) scanf("%d%d", &q.first, &q.second), q.first--, q.second--;
^
```

#### Judge Result

Score / Max Score 0 / 0 0 / 200 0 / 500
Status
 AC × 1
 AC × 4 TLE × 10
 AC × 5 TLE × 22
Set Name Test Cases
Sample example_01.txt
Case Name Status Exec Time Memory
example_01.txt AC 4 ms 256 KB
subtask1_01.txt TLE 3157 ms 256 KB
subtask1_02.txt AC 4 ms 256 KB
subtask1_03.txt TLE 3153 ms 384 KB
subtask1_04.txt AC 11 ms 384 KB
subtask1_05.txt TLE 3153 ms 384 KB
subtask1_06.txt AC 7 ms 256 KB
subtask1_07.txt TLE 3153 ms 256 KB
subtask1_08.txt TLE 3157 ms 384 KB
subtask1_09.txt TLE 3157 ms 384 KB
subtask1_10.txt TLE 3153 ms 384 KB
subtask1_11.txt TLE 3153 ms 384 KB
subtask1_12.txt TLE 3153 ms 384 KB
subtask1_13.txt TLE 3157 ms 384 KB
subtask2_01.txt TLE 3158 ms 9600 KB
subtask2_02.txt AC 766 ms 9848 KB
subtask2_03.txt TLE 3157 ms 9600 KB
subtask2_04.txt TLE 3154 ms 6528 KB
subtask2_05.txt TLE 3157 ms 6528 KB
subtask2_06.txt TLE 3154 ms 9600 KB
subtask2_07.txt TLE 3154 ms 9600 KB
subtask2_08.txt TLE 3154 ms 9600 KB
subtask2_09.txt TLE 3157 ms 9600 KB
subtask2_10.txt TLE 3158 ms 9600 KB
subtask2_11.txt TLE 3154 ms 8960 KB
subtask2_12.txt TLE 3154 ms 9600 KB
subtask2_13.txt TLE 3154 ms 9600 KB