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 <bits/stdc++.h>
using namespace std;
using i32 = int;
using i64 = long long;
template <typename T>
using V = vector<T>;
template <typename T>
using VV = V<V<T>>;
#define OVERRIDE4(a, b, c, d, ...) d
#define REP2(i, n) for (i32 i = 0; i < (i32)(n); ++i)
#define REP3(i, l, r) for (i32 i = (i32)(l); i < (i32)(r); ++i)
#define REP(...) OVERRIDE4(__VA_ARGS__, REP3, REP2)(__VA_ARGS__)
#define PER2(i, n) for (i32 i = (i32)(n) - 1; i >= 0; --i)
#define PER3(i, l, r) for (i32 i = (i32)(r) - 1; i >= (i32)(l); --i)
#define PER(...) OVERRIDE4(__VA_ARGS__, PER3, PER2)(__VA_ARGS__)
#define LEN(x) (i32)size(x)
#define ALL(x) begin(x), end(x)
template <typename T>
bool chmin(T &x, const T &y) {
if (x > y) {
x = y;
return true;
}
return false;
}
template <typename T>
bool chmax(T &x, const T &y) {
if (x < y) {
x = y;
return true;
}
return false;
}
V<i32> riffle(V<i32> a) {
V<i32> b;
b.reserve(LEN(a));
i32 l = 0, r = LEN(a) / 2;
i32 lto = r, rto = LEN(a);
while (LEN(b) < LEN(a)) {
if (r == rto || (l < lto && a[l] < a[r])) {
b.push_back(a[l++]);
} else {
b.push_back(a[r++]);
}
}
return b;
}
int main() {
i32 n, q;
cin >> n >> q;
V<i32> a(n);
REP(i, n) {
cin >> a[i];
}
V<i32> t(q), idx(q);
REP(i, q) {
cin >> t[i] >> idx[i];
--idx[i];
}
i32 to = t[0];
assert(count(ALL(t), to) == q);
i32 x = 0;
while (x < to) {
V<i32> pm(n, 0);
{
i32 mx = -1;
REP(i, n) {
if (chmax(mx, a[i])) {
pm[i] = 1;
}
}
}
if (pm[n / 2]) {
break;
}
i32 pv = n / 2 - 1;
while (!pm[pv]) {
--pv;
}
i32 rsz = 0;
while (rsz < n / 2 && !pm[n / 2 + rsz]) {
++rsz;
}
i32 ope = min(to - x, 1 + (n / 2 - pv - 1) / rsz);
REP(i, ope) {
pm[n / 2 - i * rsz] = 1;
}
VV<i32> subs;
{
i32 l = 0;
REP(i, 1, n + 1) {
if (i == n || pm[i]) {
subs.emplace_back(V<i32>(a.begin() + l, a.begin() + i));
l = i;
}
}
}
sort(ALL(subs));
a.clear();
for (const V<i32> &sub : subs) {
for (i32 ele : sub) {
a.push_back(ele);
}
}
x += ope;
}
REP(i, q) {
cout << a[idx[i]] << '\n';
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |