Submission #1105464

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105464		epicci23	Abracadabra (CEOI22_abracadabra)	C++17	10 / 100	689 ms	524288 KiB

Main

#include "bits/stdc++.h"
#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int n,q;
vector<int> ans;
vector<vector<array<int,2>>> calc;
void f(vector<int> v,int kac){
  if(kac>=2*n+2) return;
  for(auto x:calc[kac]) ans[x[1]]=v[x[0]-1];
  
  vector<int> res;
  int p1 = 0, p2 = n / 2;
  while(p1<n/2 && p2<n){
    if(v[p1]<v[p2]) res.push_back(v[p1++]);
    else res.push_back(v[p2++]);
  }
  while(p1<n/2) res.push_back(v[p1++]);
  while(p2<n) res.push_back(v[p2++]);

  f(res,kac+1);
  return;
}


void _(){
  cin >> n >> q;
  calc.resize(2*n+5);
  ans.resize(q+5);
  vector<int> ar;
  for(int i=0;i<n;i++){
    int a;cin >> a;
    ar.push_back(a);
  }
  
  for(int i=1;i<=q;i++){
    int a,b;
    cin >> a >> b;
    calc[min(2*n+1,a)].push_back({b,i});
  }

  f(ar,0);
  for(int i=1;i<=q;i++) cout << ans[i] << '\n';
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}

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