Submission #899655

#	Time	Username	Problem	Language	Result	Execution time	Memory
899655		MilosMilutinovic	Railway Trip 2 (JOI22_ho_t4)	C++14	100 / 100	1639 ms	523848 KiB

Main

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, k;
  cin >> n >> k;
  int m;
  cin >> m;
  vector<vector<vector<int>>> qs(n, vector<vector<int>>(2));
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    --a; --b;
    if (a < b) {
      qs[a][0].push_back(b);
      qs[min(b, a + k - 1)][0].push_back(~b);
    } else {
      qs[max(b, a - k + 1)][1].push_back(b);
      qs[a][1].push_back(~b);
    }
  }
  const int LOG = 20;
  vector<vector<int>> R(n, vector<int>(LOG));
  vector<vector<int>> L(n, vector<int>(LOG));
  vector<multiset<int>> st(2);
  for (int i = 0; i < n; i++) {
    for (int t = 0; t < 2; t++) {
      for (int x : qs[i][t]) {
        if (x >= 0) {
          st[t].insert(x);
        }
      }
    }
    R[i][0] = (st[0].empty() ? i : *prev(st[0].end()));
    L[i][0] = (st[1].empty() ? i : *st[1].begin());
    for (int t = 0; t < 2; t++) {
      for (int x : qs[i][t]) {
        if (x < 0) {
          x = ~x;
          st[t].erase(st[t].find(x));
        }
      }
    }
  }
  for (int j = 1; j < LOG; j++) {
    vector<vector<int>> mn(n, vector<int>(LOG));
    vector<vector<int>> mx(n, vector<int>(LOG));
    vector<int> logs(n + 1);
    for (int i = 0; i < n; i++) {
      mn[i][0] = L[i][j - 1];
      mx[i][0] = R[i][j - 1];
    }
    for (int l = 1; l < LOG; l++) {
      for (int i = 0; i + (1 << l) <= n; i++) {
        mn[i][l] = min(mn[i][l - 1], mn[i + (1 << (l - 1))][l - 1]);
        mx[i][l] = max(mx[i][l - 1], mx[i + (1 << (l - 1))][l - 1]);
      }
    }
    for (int i = 2; i <= n; i++) {
      logs[i] = logs[i >> 1] + 1;
    }
    auto QueryMin = [&](int l, int r) {
      int k = logs[r - l + 1];
      return min(mn[l][k], mn[r - (1 << k) + 1][k]);
    };
    auto QueryMax = [&](int l, int r) {
      int k = logs[r - l + 1];
      return max(mx[l][k], mx[r - (1 << k) + 1][k]);
    };
    for (int i = 0; i < n; i++) {
      L[i][j] = QueryMin(L[i][j - 1], R[i][j - 1]);
      R[i][j] = QueryMax(L[i][j - 1], R[i][j - 1]);
    }
  }
  vector<vector<vector<int>>> mn(LOG, vector<vector<int>>(n, vector<int>(LOG)));
  vector<vector<vector<int>>> mx(LOG, vector<vector<int>>(n, vector<int>(LOG)));
  vector<int> logs(n + 1);
  for (int i = 2; i <= n; i++) {
    logs[i] = logs[i >> 1] + 1;
  }
  for (int l = 0; l < LOG; l++) {
    for (int i = 0; i < n; i++) {
      mn[l][i][0] = L[i][l];
      mx[l][i][0] = R[i][l];
    }
    for (int j = 1; j < LOG; j++) {
      for (int i = 0; i + (1 << j) <= n; i++) {
        mn[l][i][j] = min(mn[l][i][j - 1], mn[l][i + (1 << (j - 1))][j - 1]);
        mx[l][i][j] = max(mx[l][i][j - 1], mx[l][i + (1 << (j - 1))][j - 1]);
      }
    }
  }
  auto QueryMin = [&](int i, int l, int r) {
    int k = logs[r - l + 1];
    return min(mn[i][l][k], mn[i][r - (1 << k) + 1][k]);
  };
  auto QueryMax = [&](int i, int l, int r) {
    int k = logs[r - l + 1];
    return max(mx[i][l][k], mx[i][r - (1 << k) + 1][k]);
  }; 
  int q;
  cin >> q;
  while (q--) {
    int a, b;
    cin >> a >> b;
    --a; --b;
    if (L[a][LOG - 1] > b || R[a][LOG - 1] < b) {
      cout << -1 << '\n';
      continue;
    }
    int cl = a, cr = a;
    int res = 1;
    for (int i = LOG - 1; i >= 0; i--) {
      if (QueryMin(i, cl, cr) <= b && QueryMax(i, cl, cr) >= b) {
        continue;
      }
      res += (1 << i);
      int new_cl = QueryMin(i, cl, cr);
      int new_cr = QueryMax(i, cl, cr);
      cl = new_cl;
      cr = new_cr;
    }
    cout << res << '\n';
  }
  return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 11 / 11
• Subtask 4: 25 / 25
• Subtask 5: 35 / 35
• Subtask 6: 13 / 13