#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);
assert(fn.S == fn.sum(n - 1));
int i = sum;
while (fn.S != sum) {
// assert(fn.S > sum);
int y = fn.lower_bound(sum + 1);
// assert(fn.lower_bound(sum + 1) > x);
// assert(y > x);
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 mx = rangeMax(l, r);
if (l == mx) {
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);
assert(l != segment[a[l]].second);
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)]);
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3073 ms |
14568 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
343 ms |
40128 KB |
Output is correct |
| 2 |
Correct |
312 ms |
40176 KB |
Output is correct |
| 3 |
Correct |
280 ms |
35524 KB |
Output is correct |
| 4 |
Correct |
248 ms |
35648 KB |
Output is correct |
| 5 |
Correct |
276 ms |
36512 KB |
Output is correct |
| 6 |
Correct |
256 ms |
35084 KB |
Output is correct |
| 7 |
Correct |
292 ms |
39932 KB |
Output is correct |
| 8 |
Correct |
291 ms |
38204 KB |
Output is correct |
| 9 |
Correct |
263 ms |
36272 KB |
Output is correct |
| 10 |
Correct |
286 ms |
38060 KB |
Output is correct |
| 11 |
Correct |
246 ms |
36124 KB |
Output is correct |
| 12 |
Correct |
228 ms |
34992 KB |
Output is correct |
| 13 |
Correct |
265 ms |
38428 KB |
Output is correct |
| 14 |
Correct |
238 ms |
36144 KB |
Output is correct |
| 15 |
Correct |
291 ms |
39272 KB |
Output is correct |
| 16 |
Correct |
44 ms |
21844 KB |
Output is correct |
| 17 |
Correct |
233 ms |
31032 KB |
Output is correct |
| 18 |
Correct |
195 ms |
35172 KB |
Output is correct |
| 19 |
Correct |
78 ms |
23620 KB |
Output is correct |
| 20 |
Correct |
95 ms |
24512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
87 ms |
13804 KB |
Output is correct |
| 2 |
Correct |
67 ms |
13220 KB |
Output is correct |
| 3 |
Correct |
83 ms |
13048 KB |
Output is correct |
| 4 |
Correct |
53 ms |
12776 KB |
Output is correct |
| 5 |
Correct |
74 ms |
13524 KB |
Output is correct |
| 6 |
Correct |
56 ms |
12676 KB |
Output is correct |
| 7 |
Correct |
61 ms |
13344 KB |
Output is correct |
| 8 |
Correct |
61 ms |
12628 KB |
Output is correct |
| 9 |
Correct |
58 ms |
13260 KB |
Output is correct |
| 10 |
Correct |
55 ms |
12400 KB |
Output is correct |
| 11 |
Correct |
48 ms |
12988 KB |
Output is correct |
| 12 |
Correct |
45 ms |
12484 KB |
Output is correct |
| 13 |
Correct |
49 ms |
12384 KB |
Output is correct |
| 14 |
Correct |
62 ms |
12832 KB |
Output is correct |
| 15 |
Correct |
43 ms |
12620 KB |
Output is correct |
| 16 |
Correct |
20 ms |
10580 KB |
Output is correct |
| 17 |
Correct |
48 ms |
11256 KB |
Output is correct |
| 18 |
Correct |
39 ms |
11760 KB |
Output is correct |
| 19 |
Correct |
1 ms |
212 KB |
Output is correct |
| 20 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3073 ms |
14568 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
