Submission #70546

#	Time	Username	Problem	Language	Result	Execution time	Memory
70546		Just_Solve_The_Problem	Railway Trip (JOI17_railway_trip)	C++11	100 / 100	378 ms	86716 KiB

railway_trip

#include <bits/stdc++.h>

using namespace std;

const int N = (int)1e5 + 7;

int n, k, q;
pair < int, int > ar[20][N];
int a[N];

main() {
  scanf("%d %d %d", &n, &k, &q);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  int que_st = 0;
  int stk[N];
  ar[0][1].first = 1;
  for (int i = 1; i <= n; i++) {
    while (que_st && a[stk[que_st]] <= a[i]) ar[0][stk[que_st--]].second = i;
    stk[++que_st] = i;
  }
  que_st = 0;
  ar[0][n].second = n;
  for (int i = n; i >= 1; i--) {
    while (que_st && a[stk[que_st]] <= a[i]) ar[0][stk[que_st--]].first = i;
    stk[++que_st] = i;
  }
  for (int i = 1; i < 20; i++) {
    for (int j = 1; j <= n; j++) {
      int x, y;
      tie(x, y) = ar[i - 1][j];
      ar[i][j] = make_pair(min(ar[i - 1][x].first, ar[i - 1][y].first), max(ar[i - 1][x].second, ar[i - 1][y].second));
    }
  }
  while (q--) {
    int l, r, ans = 0;
    scanf("%d %d", &l, &r);
    if (l > r) swap(l, r);
    int x, y;
    x = y = l;
    for (int i = 19; i >= 0; i--) {
      if (max(ar[i][x].second, ar[i][y].second) >= r) continue;
      tie(x, y) = make_pair(min(ar[i][x].first, ar[i][y].first), max(ar[i][x].second, ar[i][y].second));
      ans += (1 << i);
    }
    l = y;
    x = y = r;
    for (int i = 19; i >= 0; i--) {
      if (min(ar[i][x].first, ar[i][y].first) <= l) continue;
      tie(x, y) = make_pair(min(ar[i][x].first, ar[i][y].first), max(ar[i][x].second, ar[i][y].second));
      ans += (1 << i);
    }
    printf("%d\n", ans);
  }
}

Compilation message (stderr)

railway_trip.cpp: In function 'int main()':
railway_trip.cpp:12:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &n, &k, &q);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
railway_trip.cpp:14:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &a[i]);
     ~~~~~^~~~~~~~~~~~~
railway_trip.cpp:38:10: 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