#include <bits/stdc++.h>
using namespace std;
void riffle_shuffle(vector<int> &a) {
vector<int> L(a.begin(), a.begin() + a.size() / 2);
vector<int> R(a.begin() + a.size() / 2, a.end());
int i = 0, j = 0;
int n = a.size() / 2;
while (i < n || j < n) {
if (i != n && (j == n || L[i] < R[j])) {
a[j + i] = L[i];
i += 1;
} else {
a[j + i] = R[j];
j += 1;
}
}
}
struct Fenwick {
vector<int> t;
int n, S = 0;
Fenwick() = default;
Fenwick(int n) : n(n), t(n + 1) {}
void modify(int i, int v) {
S += v;
for (int x = i + 1; x <= n; x += x & -x) {
t[x] += v;
}
}
int sum(int i) {
int ans = 0;
for (int x = i + 1; x > 0; x -= x & -x) {
ans += t[x];
}
return ans;
}
int lower_bound(int k) {
int x = 0;
for (int i = 1 << __lg(n); i > 0; i >>= 1) {
if (x + i <= n && t[x + i] < k) {
x += i;
k -= t[x];
}
}
return x;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
vector<int> a(n);
for (int &x: a) {
cin >> x;
x -= 1;
}
vector<int> ans(q, -1);
vector<vector<array<int, 2>>> queries(n + 1);
for (int i = 0; i < q; ++i) {
int t, p;
cin >> t >> p;
p -= 1;
if (t == 0) {
ans[i] = a[p];
continue;
}
queries[min(t, n) - 1].push_back({i, p});
}
vector<int> save = a;
riffle_shuffle(save);
a = save;
const int logn = __lg(n) + 1;
auto comp = [&](int i, int j) {
return a[i] < a[j] ? i : j;
};
vector<vector<int>> mn(logn);
mn[0].resize(n);
iota(mn[0].begin(), mn[0].end(), 0);
for (int l = 1; l < logn; ++l) {
mn[l].resize(n - (1 << l) + 1);
for (int i = 0; i + (1 << l) <= n; ++i) {
mn[l][i] = comp(mn[l - 1][i], mn[l - 1][i + (1 << l - 1)]);
}
}
auto rangeMin = [&](int l, int r) {
int lg = __lg(r - l);
return comp(mn[lg][l], mn[lg][r - (1 << lg)]);
};
Fenwick fn(n);
vector<pair<int, int>> segment(n, {-1, -1});
int pref_mx = -1;
for (int i = 0; i < n / 2; ++i) {
if (pref_mx < a[i]) {
if (pref_mx != -1) {
segment[pref_mx].second = i;
}
pref_mx = a[i];
segment[pref_mx].first = i;
}
}
segment[pref_mx].second = n / 2;
pref_mx = -1;
for (int i = n / 2; i < n; ++i) {
if (pref_mx < a[i]) {
if (pref_mx != -1) {
segment[pref_mx].second = i;
}
pref_mx = a[i];
segment[pref_mx].first = i;
}
}
segment[pref_mx].second = n;
for (int x = 0; x < n; ++x) {
if (segment[x].first != -1) {
fn.modify(x, segment[x].second - segment[x].first);
}
}
vector<int> b(n, -1);
auto check = [&]() {
int x = fn.lower_bound(n / 2);
int sum = fn.sum(x);
if (sum == n / 2) {
int i = 0;
while (fn.S > 0) {
int y = fn.lower_bound(1);
for (int j = segment[y].first; j < segment[y].second; ++j) {
b[i++] = a[j];
}
fn.modify(y, -(segment[y].second - segment[y].first));
}
return true;
}
return false;
};
auto normalize = [&]() {
int x = fn.lower_bound(n / 2);
int sum = fn.sum(x);
int i = sum;
while (fn.S != sum) {
int y = fn.lower_bound(sum + 1);
for (int j = segment[y].first; j < segment[y].second; ++j) {
b[i++] = a[j];
}
fn.modify(y, -(segment[y].second - segment[y].first));
}
};
auto find_next = [&](int l, int r) {
int mn = rangeMin(l, r);
if (l == mn) {
return -1;
}
int lo = l, hi = r;
while (lo + 1 < hi) {
int mid = (lo + hi) >> 1;
if (rangeMin(l, mid) == l) {
lo = mid;
} else {
hi = mid;
}
}
return hi;
};
auto getValue = [&](int p) {
if (b[p] != -1) {
return b[p];
}
p += 1;
int x = fn.lower_bound(p);
int sum_l = fn.sum(x - 1);
return a[segment[x].first + (p - sum_l) - 1];
};
auto print = [&]() {
cout << "save: ";
for (int x: save) cout << x + 1 << " ";
cout << '\n';
cout << "a : ";
for (int i = 0; i < n; ++i) {
cout << getValue(i) + 1 << " ";
}
cout << endl << endl;
};
normalize();
for (auto [i, p] : queries[0]) {
ans[i] = save[p];
}
for (int _ = 1; _ < n; ++_) {
if (b[0] == -1) {
if (!check()) {
int x = fn.lower_bound(n / 2);
int sum = fn.sum(x);
int sum_l = sum - (segment[x].second - segment[x].first);
assert(sum_l < n / 2);
int cut = segment[x].first + (n / 2 - sum_l);
fn.modify(x, -(segment[x].second - cut));
int l = cut, r = segment[x].second;
segment[x].second = cut;
while (l < r) {
int mid = find_next(l, r);
if (mid == -1) {
segment[a[l]].first = l, segment[a[l]].second = r;
} else {
segment[a[l]].first = l, segment[a[l]].second = mid;
}
fn.modify(a[l], segment[a[l]].second - segment[a[l]].first);
l = segment[a[l]].second;
}
normalize();
}
}
riffle_shuffle(save);
//
print();
for (auto [i, p]: queries[_]) {
ans[i] = save[p]; //getValue(p);
}
}
for (int i = 0; i < q; ++i) {
cout << ans[i] + 1 << '\n';
}
return 0;
}
Compilation message
Main.cpp: In constructor 'Fenwick::Fenwick(int)':
Main.cpp:25:9: warning: 'Fenwick::n' will be initialized after [-Wreorder]
25 | int n, S = 0;
| ^
Main.cpp:24:17: warning: 'std::vector<int> Fenwick::t' [-Wreorder]
24 | vector<int> t;
| ^
Main.cpp:29:5: warning: when initialized here [-Wreorder]
29 | Fenwick(int n) : n(n), t(n + 1) {}
| ^~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:109:65: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
109 | mn[l][i] = comp(mn[l - 1][i], mn[l - 1][i + (1 << l - 1)]);
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
372 ms |
26164 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3087 ms |
269832 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3085 ms |
238260 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
372 ms |
26164 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
