Submission #37961704

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

vector<pair<int, int>> vec;

void f(int L, int R) {
  if (L == R) {
    vec.push_back(make_pair(L, R));
    return;
  }
  int m = (L + R) / 2;
  for (int i = L; i <= m; i++) vec.push_back(make_pair(i, m));
  for (int i = m + 1; i <= R; i++) vec.push_back(make_pair(m + 1, i));
  f(L, m);
  f(m + 1, R);
  return;
}

int main() {
  // Phase 1
  int n;
  cin >> n;

  f(1, n);
  sort(vec.begin(), vec.end());
  vec.erase(unique(vec.begin(), vec.end()), vec.end());

  int m = vec.size();
  cout << m << endl;
  for (auto i : vec) {
    cout << i.first << " " << i.second << endl;
  }

  // preprocess
  vector<vector<pair<int, int>>> left2right(n + 1), right2left(n + 1);
  // left2right[i]: Phase 1で準備した区間のうち、左端の数がiであるようなものの（右端の数, 添字）のペアの配列
  // right2left[i]: 右端の数がiであるようなものの（左端の数, 添字）のペアの配列

  for (int i = 0; i < m; i++) {
    left2right[vec[i].first].push_back(make_pair(vec[i].second, i + 1));
    right2left[vec[i].second].push_back(make_pair(vec[i].first, i + 1));
  }
  for (int i = 1; i <= n; i++) {
    sort(left2right[i].begin(), left2right[i].end());
    sort(right2left[i].begin(), right2left[i].end());
  }

  // Phase 2
  int q;
  cin >> q;

  while (q--) {
    int l, r;
    cin >> l >> r;
    if (l == r) {
      cout << left2right[l][0].second << " " << left2right[l][0].second << endl;
      continue;
    }
    int itr = 0;
    for (auto i : left2right[l]) {
      while (right2left[r][itr].first <= i.first) itr++;
      if (i.first + 1 == right2left[r][itr].first) {
        cout << i.second << " " << right2left[r][itr].second << endl;
        break;
      }
    }
  }

}

Submission Info

Judge Result