oj.uz

Submission #1105464

# Submission time Handle Problem Language Result Execution time Memory
1105464 2024-10-26T13:11:10 Z epicci23 Abracadabra (CEOI22_abracadabra) C++17
10 / 100
 689 ms 524288 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 65476 KB Output is correct
2 Correct 197 ms 64072 KB Output is correct
3 Correct 169 ms 62152 KB Output is correct
4 Correct 168 ms 60240 KB Output is correct
5 Correct 181 ms 65988 KB Output is correct
6 Correct 172 ms 62276 KB Output is correct
7 Correct 213 ms 67656 KB Output is correct
8 Correct 191 ms 60776 KB Output is correct
9 Correct 202 ms 61860 KB Output is correct
10 Correct 188 ms 59716 KB Output is correct
11 Correct 185 ms 61680 KB Output is correct
12 Correct 170 ms 64344 KB Output is correct
13 Correct 207 ms 59396 KB Output is correct
14 Correct 193 ms 62432 KB Output is correct
15 Correct 201 ms 61124 KB Output is correct
16 Correct 56 ms 32072 KB Output is correct
17 Correct 173 ms 60412 KB Output is correct
18 Correct 166 ms 60324 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 1 ms 336 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 633 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 689 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 65476 KB Output is correct
2 Correct 197 ms 64072 KB Output is correct
3 Correct 169 ms 62152 KB Output is correct
4 Correct 168 ms 60240 KB Output is correct
5 Correct 181 ms 65988 KB Output is correct
6 Correct 172 ms 62276 KB Output is correct
7 Correct 213 ms 67656 KB Output is correct
8 Correct 191 ms 60776 KB Output is correct
9 Correct 202 ms 61860 KB Output is correct
10 Correct 188 ms 59716 KB Output is correct
11 Correct 185 ms 61680 KB Output is correct
12 Correct 170 ms 64344 KB Output is correct
13 Correct 207 ms 59396 KB Output is correct
14 Correct 193 ms 62432 KB Output is correct
15 Correct 201 ms 61124 KB Output is correct
16 Correct 56 ms 32072 KB Output is correct
17 Correct 173 ms 60412 KB Output is correct
18 Correct 166 ms 60324 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 1 ms 336 KB Output is correct
21 Runtime error 633 ms 524288 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -