Submission #857358


Source Code Expand

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

int main() {
  int n, q, l, a, b;
  int x[100000];
  std::vector<std::vector<int>> next;
  std::scanf("%d", &n);
  for (int ni = 0; ni < n; ++ni) {
    std::scanf("%d", &x[ni]);
  }
  std::scanf("%d%d", &l, &q);
  next.resize(n, std::vector<int>(25));
  for (int ni = 0; ni < n; ++ni) {
    int inf = ni;
    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 < 25; ++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::scanf("%d%d", &a, &b);
    if (a > b) {
      std::swap(a, b);
    }
    --a;
    --b;
    while (a < b) {
      for (int d = 1; d < 25; ++d) {
        if (next[a][d] > b or next[a][d - 1] == next[a][d]) {
          a = next[a][d];
          ans += 1 << (d - 1);
          break;
        }
      }
    }
    std::printf("%d\n", ans);
  }
  return 0;
}

Submission Info

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

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 0 / 200 0 / 500
Status
AC × 1
AC × 3
WA × 11
AC × 5
WA × 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 8 ms 888 KB
subtask1_01.txt WA 4 ms 256 KB
subtask1_02.txt AC 4 ms 256 KB
subtask1_03.txt WA 5 ms 384 KB
subtask1_04.txt WA 5 ms 384 KB
subtask1_05.txt WA 5 ms 384 KB
subtask1_06.txt WA 4 ms 384 KB
subtask1_07.txt WA 4 ms 384 KB
subtask1_08.txt AC 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 146 ms 14336 KB
subtask2_02.txt WA 151 ms 14464 KB
subtask2_03.txt WA 146 ms 14336 KB
subtask2_04.txt AC 96 ms 9344 KB
subtask2_05.txt WA 95 ms 9472 KB
subtask2_06.txt AC 137 ms 14080 KB
subtask2_07.txt WA 147 ms 14336 KB
subtask2_08.txt WA 147 ms 14464 KB
subtask2_09.txt WA 147 ms 14464 KB
subtask2_10.txt WA 147 ms 14464 KB
subtask2_11.txt WA 140 ms 13440 KB
subtask2_12.txt WA 137 ms 14464 KB
subtask2_13.txt WA 138 ms 14080 KB