Submission #1188037

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188037		lopkus	Abracadabra (CEOI22_abracadabra)	C++20	0 / 100	980 ms	18312 KiB

Main

#include <bits/stdc++.h>

const int B = 1001;


void solve() {
  int n, q;
  std::cin >> n >> q;
  std::vector<int> a(n + 1);
  for(int i = 1; i <= n; i++) {
    std::cin >> a[i];
  }
  std::vector<std::pair<int,int>> queries[B];
  std::vector<int> ans(q + 1, - 1);
  for(int i = 1; i <= q; i++) {
    int t, pos;
    std::cin >> t >> pos;
    if(t >= B) {
      ans[i] = pos;
    }
    else {
      queries[t].push_back({pos, i});
    }
  }
  std::vector<int> b = a;
  std::function<void()> Do = [&] () {
    int l = 1;
    int r = n / 2 + 1;
    std::vector<int> New;
    New.push_back(- 1);
    while(l <= n / 2 || r <= n) {
      if(l > n / 2) {
        New.push_back(b[r++]);
        continue;
      }
      if(r > n) {
        New.push_back(b[l++]);
        continue;
      }
      if(b[l] < b[r]) {
        New.push_back(b[l++]);
      }
      else {
        New.push_back(b[r++]);
      }
    }
    b = New;
  };
  for(int T = 0; T < B; T++) {
    for(auto [pos, i] : queries[T]) {
      ans[i] = b[pos];
    }
    Do();
  }
  for(int i = 1; i <= q; i++) {
    std::cout << ans[i] << "\n";
  }
}

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

  int t = 1;
  //std::cin >> t;
  while (t--) {
      solve();
  }

  return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 40
• Subtask 3: 0 / 25
• Subtask 4: 0 / 25