Submission #1215029

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215029		zfs732	OGLEDALA (COI15_ogledala)	C++20	100 / 100	1538 ms	200568 KiB

ogledala

/*
 * _|_|_|_|_|  _|_|_|_|    _|_|_|  _|_|_|_|_|  _|_|_|      _|_|
 *       _|    _|        _|                _|        _|  _|    _|
 *     _|      _|_|_|      _|_|          _|      _|_|        _|
 *   _|        _|              _|      _|            _|    _|
 * _|_|_|_|_|  _|        _|_|_|      _|        _|_|_|    _|_|_|_|
 */

#include <bits/stdc++.h>

auto Split(long long len) {
  std::vector<std::pair<long long, long long>> gt;
  if (len == 0) { return gt; }

  gt.emplace_back(len + 1, 0);
  gt.emplace_back(len, 1);
  for (int i = 0; i < gt.size(); i += 2) {
    long long nlen1 = gt[i].first / 2, ncnt1 = gt[i].second;
    long long nlen2 = (gt[i + 1].first - 1) / 2, ncnt2 = gt[i + 1].second;
    if ((gt[i].first - 1) / 2 == nlen1) {
      ncnt1 += gt[i].second;
    } else {
      ncnt2 += gt[i].second;
    }
    if (gt[i + 1].first / 2 == nlen1) {
      ncnt1 += gt[i + 1].second;
    } else {
      ncnt2 += gt[i + 1].second;
    }
    if (!nlen1 && !nlen2) { break; }
    gt.emplace_back(nlen1, ncnt1);
    gt.emplace_back(nlen2, ncnt2);
  }

  for (; !gt.empty() && gt.back().first == 0; gt.pop_back()) {}
  long long cnt1 = 0;
  for (; !gt.empty() && gt.back().first == 1; gt.pop_back()) {
    cnt1 += gt.back().second;
  }
  if (cnt1) { gt.emplace_back(1, cnt1); }

  return gt;
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  long long M;
  int N, Q;
  std::cin >> M >> N >> Q;
  std::vector<long long> A(N), C{-1, M}, ans(Q);
  std::vector<std::tuple<long long, int, long long>> arr;
  std::vector<std::pair<long long, int>> qur;

  for (auto &v: A) { std::cin >> v, v--, C.emplace_back(v); }

  std::ranges::sort(C);
  for (int i = 1; i <= N + 1; i++) {
    if (C[i - 1] != C[i]) {
      auto pt = Split(C[i] - C[i - 1] - 1);
      for (auto [len, cnt]: pt) {
        if (cnt) { arr.emplace_back(-len, i, cnt); }
      }
    }
  }

  std::ranges::sort(arr);

  for (int i = 0; i < Q; i++) {
    long long x;
    std::cin >> x, x--;
    qur.emplace_back(x, i);
  }

  std::ranges::sort(qur);

  long long ti = N;
  auto it = arr.begin();
  for (auto [x, id]: qur) {
    while (it != arr.end() && ti + std::get<2>(*it) <= x) {
      ti += std::get<2>(*it++);
    }
    if (x < N) {
      ans[id] = A[x];
    } else {
      auto [len, tid, cnt] = *it;
      len = -len, x -= ti;
      long long tlen = C[tid] - C[tid - 1] - 1, st = C[tid - 1] + 1;
      while (tlen != len) {
        auto pt = Split((tlen - 1) / 2);
        bool ok = false;
        for (auto [nlen, ncnt]: pt) {
          if (nlen == len) {
            if (ncnt > x) {
              ok = true;
            } else {
              x -= ncnt;
            }
            break;
          }
        }
        if (!ok) {
          st += (tlen + 1) / 2;
          tlen = tlen / 2;
        } else {
          tlen = (tlen - 1) / 2;
        }
      }
      ans[id] = st + (len - 1) / 2;
    }
  }

  for (auto v: ans) { std::cout << v + 1 << '\n'; }

  return 0;
}

• Subtask 1: 19 / 19
• Subtask 2: 22 / 22
• Subtask 3: 59 / 59