Submission #856121


Source Code Expand

Copy
#include <algorithm>
#include <iostream>
#include <numeric>
#include <string>
#include <utility>
#include <vector>

int main() {
  int n, q, a, b;
  long long l;
  long long x[100000];
  std::vector<std::vector<int>> next(100000, std::vector<int>(20));
  std::cin >> n;
  for (int ni = 0; ni < n; ++ni) {
    std::cin >> x[ni];
  }
  std::cin >> l >> q;
  for (int ni = 0; ni < n; ++ni) {
    int inf = 0;
    int sup = n;
    while (sup - inf > 1) {
      int c = (inf + sup) / 2;
      if (x[c] <= x[ni] + l) {
        inf = c;
      } else {
        sup = c;
      }
    }
    next[ni][0] = inf;
  }
  for (int c = 1; c < 20; ++c) {
    for (int ni = 0; ni < n; ++ni) {
      next[ni][c] = next[next[ni][c - 1]][c - 1];
    }
  }
  for (int qi = 0; qi < q; ++qi) {
    int ans = 0;
    std::cin >> a >> b;
    if (a > b) {
      std::swap(a, b);
    }
    --a;
    --b;
    while (a < b) {
      for (int d = 19; d >= 0; --d) {
        if (next[a][d] <= b) {
          a = next[a][d] + 1;
          ans += 1 << d;
          break;
        }
      }
    }
    std::cout << ans << std::endl;
  }
  return 0;
}

Submission Info

Submission Time
Task E - Tak and Hotels
User saltcandy123
Language C++14 (Clang 3.8.0)
Score 0
Code Size 1165 Byte
Status WA
Exec Time 3158 ms
Memory 13312 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 0 / 200 0 / 500
Status
AC × 1
AC × 1
WA × 3
TLE × 10
AC × 1
WA × 4
TLE × 22
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 35 ms 12536 KB
subtask1_01.txt TLE 3154 ms 12032 KB
subtask1_02.txt WA 36 ms 12032 KB
subtask1_03.txt TLE 3154 ms 12032 KB
subtask1_04.txt WA 40 ms 12032 KB
subtask1_05.txt TLE 3154 ms 12032 KB
subtask1_06.txt WA 39 ms 12032 KB
subtask1_07.txt TLE 3158 ms 12032 KB
subtask1_08.txt TLE 3158 ms 12032 KB
subtask1_09.txt TLE 3154 ms 12032 KB
subtask1_10.txt TLE 3154 ms 12032 KB
subtask1_11.txt TLE 3154 ms 12032 KB
subtask1_12.txt TLE 3154 ms 12032 KB
subtask1_13.txt TLE 3158 ms 12032 KB
subtask2_01.txt TLE 3158 ms 12800 KB
subtask2_02.txt WA 1394 ms 13312 KB
subtask2_03.txt TLE 3154 ms 12800 KB
subtask2_04.txt TLE 3154 ms 12544 KB
subtask2_05.txt TLE 3158 ms 12544 KB
subtask2_06.txt TLE 3158 ms 12800 KB
subtask2_07.txt TLE 3154 ms 12800 KB
subtask2_08.txt TLE 3154 ms 12800 KB
subtask2_09.txt TLE 3154 ms 12800 KB
subtask2_10.txt TLE 3158 ms 12800 KB
subtask2_11.txt TLE 3154 ms 12672 KB
subtask2_12.txt TLE 3154 ms 12800 KB
subtask2_13.txt TLE 3154 ms 12800 KB