Submission #24326

#	Time	Username	Problem	Language	Result	Execution time	Memory
24326		jiaqiyang	Railway Trip (JOI17_railway_trip)	C++14	100 / 100	396 ms	17524 KiB

railway_trip

#include <cstdio>
#include <tuple>
#include <algorithm>

const int N = 100000 + 10;

int n, a[N];

std::pair<int, int> f[20][N];

int init() {
  int q;
  scanf("%d%*d%d", &n, &q);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  static int stk[N];
  f[0][n].second = n;
  for (int i = 1, top = 0; i <= n; ++i) {
    for (; top && a[i] >= a[stk[top]]; --top) f[0][stk[top]].second = i;
    stk[++top] = i;
  }
  f[0][1].first = 1;
  for (int i = n, top = 0; i > 0; --i) {
    for (; top && a[i] >= a[stk[top]]; --top) f[0][stk[top]].first = i;
    stk[++top] = i;
  }
  for (int i = 1; i < 20; ++i) {
    for (int j = 1; j <= n; ++j) {
      int x, y;
      std::tie(x, y) = f[i - 1][j];
      f[i][j] = {std::min(f[i - 1][x].first, f[i - 1][y].first), std::max(f[i - 1][x].second, f[i - 1][y].second)};
    }
  }
  return q;
}

int main() {
  for (int q = init(); q--;) {
    int l, r;
    scanf("%d%d", &l, &r);
    if (l > r) std::swap(l, r);
    int ans = 0, x = l, y = l;
    for (int i = 19; i >= 0; --i) {
      if (std::max(f[i][x].second, f[i][y].second) >= r) continue;
      ans += 1 << i;
      std::tie(x, y) = std::make_tuple(std::min(f[i][x].first, f[i][y].first), std::max(f[i][x].second, f[i][y].second));
    }
    l = y;
    x = y = r;
    for (int i = 19; i >= 0; --i) {
      if (std::min(f[i][x].first, f[i][y].first) <= l) continue;
      ans += 1 << i;
      std::tie(x, y) = std::make_tuple(std::min(f[i][x].first, f[i][y].first), std::max(f[i][x].second, f[i][y].second));
    }
    printf("%d\n", ans);
  }
  return 0;
}

Compilation message (stderr)

railway_trip.cpp: In function 'int init()':
railway_trip.cpp:13:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%*d%d", &n, &q);
                           ^
railway_trip.cpp:14:50: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
                                                  ^
railway_trip.cpp: In function 'int main()':
railway_trip.cpp:39:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &l, &r);
                          ^

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 25 / 25
• Subtask 4: 55 / 55