Submission #856849


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 = 24; true; --d) {
        if (d < 0) {
          return -1;
        }
        if (next[a][d] <= b) {
          a = next[a][d];
          ans += 1 << d;
          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 1230 Byte
Status WA
Exec Time 223 ms
Memory 14464 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 0 / 200 0 / 500
Status
AC × 1
AC × 1
WA × 3
RE × 10
AC × 1
WA × 4
RE × 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 4 ms 256 KB
subtask1_01.txt RE 4 ms 256 KB
subtask1_02.txt WA 4 ms 256 KB
subtask1_03.txt RE 4 ms 384 KB
subtask1_04.txt WA 5 ms 384 KB
subtask1_05.txt RE 5 ms 384 KB
subtask1_06.txt WA 5 ms 384 KB
subtask1_07.txt RE 4 ms 384 KB
subtask1_08.txt RE 4 ms 384 KB
subtask1_09.txt RE 4 ms 384 KB
subtask1_10.txt RE 4 ms 384 KB
subtask1_11.txt RE 4 ms 384 KB
subtask1_12.txt RE 4 ms 384 KB
subtask1_13.txt RE 4 ms 384 KB
subtask2_01.txt RE 84 ms 13952 KB
subtask2_02.txt WA 223 ms 14464 KB
subtask2_03.txt RE 89 ms 13952 KB
subtask2_04.txt RE 57 ms 9216 KB
subtask2_05.txt RE 56 ms 9216 KB
subtask2_06.txt RE 87 ms 13952 KB
subtask2_07.txt RE 88 ms 13952 KB
subtask2_08.txt RE 87 ms 13952 KB
subtask2_09.txt RE 87 ms 13952 KB
subtask2_10.txt RE 88 ms 13952 KB
subtask2_11.txt RE 80 ms 12800 KB
subtask2_12.txt RE 89 ms 13952 KB
subtask2_13.txt RE 85 ms 13952 KB