Submission #911695


Source Code Expand

Copy
#include <algorithm>
#include <cstdio>
#include <vector>

int main() {
  int n, l, q, a, b, left, right;
  int x[100000];
  std::vector<int> next[30];
  std::scanf("%d", &n);
  for (int ni = 0; ni < n; ++ni) {
    std::scanf("%d", &x[ni]);
  }
  std::scanf("%d%d", &l, &q);
  next[0].resize(n);
  for (int ni = 0; ni < n; ++ni) {
    int lower = ni;
    int upper = n;
    while (upper - lower > 1) {
      int pos = (lower + upper) / 2;
      if (x[pos] - x[ni] <= l) {
        lower = pos;
      } else {
        upper = pos;
      }
    }
    next[0][ni] = lower;
  }
  for (int k = 1; k < 30; ++k) {
    next[k].resize(n);
    for (int ni = 0; ni < n; ++ni) {
      next[k][ni] = next[k - 1][next[k - 1][ni]];
    }
  }
  for (int qi = 0; qi < q; ++qi) {
    int ans = 0;
    std::scanf("%d%d", &a, &b);
    left = std::min(a - 1, b - 1);
    right = std::max(a - 1, b - 1);
    for (int k = 29; k >= 0; --k) {
      if (next[k][left] < right) {
        left = next[k][left];
        ans += (1 << k);
      }
    }
    while (left < right) {
      left = next[0][left];
      ++ans;
    }
    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 700
Code Size 1191 Byte
Status AC
Exec Time 129 ms
Memory 12928 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 200 / 200 500 / 500
Status
AC × 1
AC × 14
AC × 27
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 3 ms 256 KB
subtask1_01.txt AC 3 ms 256 KB
subtask1_02.txt AC 3 ms 256 KB
subtask1_03.txt AC 3 ms 384 KB
subtask1_04.txt AC 3 ms 384 KB
subtask1_05.txt AC 3 ms 384 KB
subtask1_06.txt AC 3 ms 384 KB
subtask1_07.txt AC 3 ms 384 KB
subtask1_08.txt AC 3 ms 384 KB
subtask1_09.txt AC 3 ms 384 KB
subtask1_10.txt AC 3 ms 384 KB
subtask1_11.txt AC 3 ms 384 KB
subtask1_12.txt AC 3 ms 384 KB
subtask1_13.txt AC 3 ms 384 KB
subtask2_01.txt AC 124 ms 12800 KB
subtask2_02.txt AC 126 ms 12928 KB
subtask2_03.txt AC 126 ms 12800 KB
subtask2_04.txt AC 80 ms 8448 KB
subtask2_05.txt AC 82 ms 8576 KB
subtask2_06.txt AC 125 ms 12672 KB
subtask2_07.txt AC 129 ms 12928 KB
subtask2_08.txt AC 127 ms 12928 KB
subtask2_09.txt AC 126 ms 12928 KB
subtask2_10.txt AC 127 ms 12928 KB
subtask2_11.txt AC 123 ms 11904 KB
subtask2_12.txt AC 81 ms 12928 KB
subtask2_13.txt AC 123 ms 12544 KB