#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;
}
};
#define STRESS 0
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
vector<int> a(n);
if (!STRESS) {
for (int &x: a) {
cin >> x;
x -= 1;
}
} else {
iota(a.begin(), a.end(), 0);
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
shuffle(a.begin(), a.end(), rnd);
}
cerr << "initial: ";
for (int x : a) cerr << x + 1 << " ";
cerr << endl;
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)].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>> mx(logn);
mx[0].resize(n);
iota(mx[0].begin(), mx[0].end(), 0);
for (int l = 1; l < logn; ++l) {
mx[l].resize(n - (1 << l) + 1);
for (int i = 0; i + (1 << l) <= n; ++i) {
mx[l][i] = comp(mx[l - 1][i], mx[l - 1][i + (1 << l - 1)]);
}
}
auto rangeMax = [&](int l, int r) {
int lg = __lg(r - l);
return comp(mx[lg][l], mx[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) {
assert(b[i] == -1);
b[i++] = a[j];
}
fn.modify(y, -(segment[y].second - segment[y].first));
}
};
auto find_next = [&](int l, int r) {
int mn = rangeMax(l, r);
if (l == mn) {
return -1;
}
int lo = l, hi = r;
while (lo + 1 < hi) {
int mid = (lo + hi) >> 1;
if (rangeMax(l, mid + 1) == 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 = [&]() {
cerr << "save: ";
for (int x: save) cerr << x + 1 << " ";
cerr << '\n';
cerr << "a : ";
for (int i = 0; i < n; ++i) {
cerr << getValue(i) + 1 << " ";
}
cerr << endl << endl;
for (int i = 0; i < n; ++i) {
assert(getValue(i) == save[i]);
}
};
normalize();
for (int _ = 1; _ <= n; ++_) {
normalize();
check();
// riffle_shuffle(save);
// print();
for (auto [i, p]: queries[_]) {
ans[i] = getValue(p);
}
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, cut - segment[x].second);
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();
}
}
}
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:122:65: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
122 | mx[l][i] = comp(mx[l - 1][i], mx[l - 1][i + (1 << l - 1)]);
| ~~^~~
Main.cpp:237:10: warning: variable 'print' set but not used [-Wunused-but-set-variable]
237 | auto print = [&]() {
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
623 ms |
19116 KB |
Output is correct |
| 2 |
Execution timed out |
3039 ms |
14004 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
808 ms |
42760 KB |
Output is correct |
| 2 |
Correct |
826 ms |
55828 KB |
Output is correct |
| 3 |
Correct |
800 ms |
48124 KB |
Output is correct |
| 4 |
Correct |
747 ms |
48552 KB |
Output is correct |
| 5 |
Correct |
746 ms |
49476 KB |
Output is correct |
| 6 |
Correct |
755 ms |
47792 KB |
Output is correct |
| 7 |
Correct |
761 ms |
55464 KB |
Output is correct |
| 8 |
Correct |
745 ms |
53036 KB |
Output is correct |
| 9 |
Correct |
715 ms |
49248 KB |
Output is correct |
| 10 |
Correct |
731 ms |
51948 KB |
Output is correct |
| 11 |
Correct |
699 ms |
47552 KB |
Output is correct |
| 12 |
Correct |
722 ms |
46788 KB |
Output is correct |
| 13 |
Correct |
727 ms |
51372 KB |
Output is correct |
| 14 |
Correct |
698 ms |
48336 KB |
Output is correct |
| 15 |
Correct |
779 ms |
53440 KB |
Output is correct |
| 16 |
Correct |
493 ms |
25196 KB |
Output is correct |
| 17 |
Correct |
679 ms |
42320 KB |
Output is correct |
| 18 |
Correct |
706 ms |
44796 KB |
Output is correct |
| 19 |
Correct |
549 ms |
28492 KB |
Output is correct |
| 20 |
Correct |
537 ms |
30796 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
328 ms |
15320 KB |
Output is correct |
| 2 |
Correct |
291 ms |
16000 KB |
Output is correct |
| 3 |
Correct |
328 ms |
15596 KB |
Output is correct |
| 4 |
Correct |
268 ms |
15680 KB |
Output is correct |
| 5 |
Correct |
302 ms |
16144 KB |
Output is correct |
| 6 |
Correct |
281 ms |
15144 KB |
Output is correct |
| 7 |
Correct |
297 ms |
16044 KB |
Output is correct |
| 8 |
Correct |
283 ms |
15192 KB |
Output is correct |
| 9 |
Correct |
281 ms |
15816 KB |
Output is correct |
| 10 |
Correct |
257 ms |
14952 KB |
Output is correct |
| 11 |
Correct |
273 ms |
15532 KB |
Output is correct |
| 12 |
Correct |
260 ms |
14956 KB |
Output is correct |
| 13 |
Correct |
286 ms |
14812 KB |
Output is correct |
| 14 |
Correct |
291 ms |
15360 KB |
Output is correct |
| 15 |
Correct |
259 ms |
15080 KB |
Output is correct |
| 16 |
Correct |
240 ms |
12160 KB |
Output is correct |
| 17 |
Correct |
262 ms |
13496 KB |
Output is correct |
| 18 |
Correct |
275 ms |
14024 KB |
Output is correct |
| 19 |
Correct |
0 ms |
212 KB |
Output is correct |
| 20 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
623 ms |
19116 KB |
Output is correct |
| 2 |
Execution timed out |
3039 ms |
14004 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
