| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 784660 | boris_mihov | Abracadabra (CEOI22_abracadabra) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <cstring>
#include <vector>
#include <cmath>
#include <stack>
typedef long long llong;
const int MAXN = 200000 + 10;
const int MAXQ = 1000000 + 10;
const llong INF = 1e18;
const int INTINF = 1e9;
int n, q;
llong total;
int a[MAXN];
int b[MAXN];
int output[MAXQ];
std::vector <std::pair <int,int>> v[MAXN];
void riffle()
{
int pos = 1;
int lPtr = 1, rPtr = n / 2 + 1;
while (lPtr < n / 2 + 1 || rPtr < n + 1)
{
if (lPtr == n / 2 + 1)
{
b[pos++] = a[rPtr++];
total = std::max(total, pos);
continue;
}
if (rPtr == n + 1)
{
b[pos++] = a[lPtr++];
continue;
}
if (a[lPtr] < a[rPtr])
{
b[pos++] = a[lPtr++];
} else
{
b[pos++] = a[rPtr++];
total = std::max(total, pos);
}
}
for (int i = 1 ; i <= n ; ++i)
{
a[i] = b[i];
}
}
void solve()
{
int bucketSize = sqrt(n) + 5;
for (int i = 0 ; i <= bucketSize ; ++i)
{
for (const auto &[pos, idx] : v[i])
{
output[idx] = a[pos];
}
riffle();
}
total = 0;
for (int i = bucketSize + 1 ; i <= n ; ++i)
{
for (const auto &[pos, idx] : v[i])
{
output[idx] = a[pos];
}
riffle();
}
assert(total <= bucketSize);
}
void print()
{
for (int i = 1 ; i <= q ; ++i)
{
std::cout << output[i] << '\n';
}
}
void input()
{
std::cin >> n >> q;
for (int i = 1 ; i <= n ; ++i)
{
std::cin >> a[i];
}
for (int i = 1 ; i <= q ; ++i)
{
int t, idx;
std::cin >> t >> idx;
v[std::min(t, (int)sqrt(n))].push_back({idx, i});
}
}
void fastIOI()
{
std::ios_base :: sync_with_stdio(0);
std::cout.tie(nullptr);
std::cin.tie(nullptr);
}
int main()
{
fastIOI();
input();
solve();
print();
return 0;
}