#include <bits/stdc++.h>
using i64 = long long;
void naive(int N, int Q, std::vector<int> P, std::vector<std::pair<i64, int>> queries) {
std::vector<std::vector<int>> states;
states.push_back(P);
while (true) {
const auto &a = states.back();
std::vector<int> x, y;
std::copy(a.begin(), a.begin() + (N / 2), std::back_inserter(x));
std::copy(a.begin() + (N / 2), a.end(), std::back_inserter(y));
std::vector<int> nextPerm;
int j = 0;
for (int i = 0; i < N / 2; ++i) {
while (j != N / 2 and y[j] < x[i]) {
nextPerm.push_back(y[j++]);
}
nextPerm.push_back(x[i]);
}
while (j != N / 2) {
nextPerm.push_back(y[j++]);
}
if (nextPerm == a) {
break;
}
states.push_back(nextPerm);
}
for (const auto &[t, i] : queries) {
if (t < (int)states.size()) {
std::cout << states[t][i] << std::endl;
} else {
std::cout << states.back()[i] << std::endl;
}
}
}
constexpr int B = 400;
struct SuperArray {
std::vector<std::vector<int>> data;
std::vector<int> maxVal;
int blocks, countOp;
SuperArray(std::vector<int> A) {
data.push_back(A);
rebuild();
}
void rebuild() {
std::vector<int> a;
for (auto &vec : data) {
std::copy(vec.begin(), vec.end(), std::back_inserter(a));
}
data.clear();
const int n = (int)a.size();
blocks = (n + B - 1) / B;
data.resize(blocks);
maxVal.assign(blocks, -1);
for (int x = 0; x < blocks; ++x) {
for (int i = x * B; i < std::min((x + 1) * B, n); ++i) {
data[x].push_back(a[i]);
maxVal[x] = std::max(maxVal[x], a[i]);
}
}
countOp = 0;
}
void incOp() {
++countOp;
if (countOp >= B) {
rebuild();
}
}
int get(int i) {
incOp();
int sum = 0;
int ret = -1;
for (const auto &vec : data) {
if (sum + (int)vec.size() <= i) {
sum += (int)vec.size();
} else {
ret = vec[i - sum];
break;
}
}
return ret;
}
void recalc(int x) {
maxVal[x] = -1;
for (const auto e : data[x]) {
maxVal[x] = std::max(maxVal[x], e);
}
}
void erase(int i) {
incOp();
int sum = 0;
for (int x = 0; x < blocks; ++x) {
auto &vec = data[x];
if (sum + (int)vec.size() <= i) {
sum += (int)vec.size();
} else {
vec.erase(vec.begin() + (i - sum));
recalc(x);
break;
}
}
}
int find(int l, int v) {
incOp();
int sum = 0;
for (int x = 0; x < blocks; ++x) {
if (sum + (int)data[x].size() <= l or maxVal[x] < v) {
sum += (int)data[x].size();
} else {
for (int i = std::max(0, l - sum); i < (int)data[x].size(); ++i) {
if (data[x][i] >= v) {
return sum + i;
}
}
}
}
return sum;
}
void insert(int i, int v) {
incOp();
int sum = 0;
for (int x = 0; x < blocks; ++x) {
auto &vec = data[x];
if (sum + (int)vec.size() <= i) {
sum += (int)vec.size();
} else {
vec.insert(vec.begin() + (i - sum), v);
recalc(x);
break;
}
}
}
void debug() {
std::vector<int> a;
for (auto &vec : data) {
std::copy(vec.begin(), vec.end(), std::back_inserter(a));
}
for (const auto e : a) {
std::cout << e << ' ';
}
std::cout << std::endl;
}
};
struct Query {
i64 t;
int i;
int queryId;
};
void solve(int N, int Q, std::vector<int> P, std::vector<std::pair<i64, int>> queries) {
std::vector<Query> qs(Q);
for (int i = 0; i < Q; ++i) {
qs[i] = {queries[i].first, queries[i].second, i};
}
std::sort(qs.begin(), qs.end(), [](auto a, auto b) {
return a.t < b.t;
});
SuperArray ar(P);
std::vector<int> answer(Q);
auto answerQuery = [&](const int t) {
static int i = 0;
if (t == -1) {
while (i != Q) {
answer[qs[i].queryId] = ar.get(qs[i].i);
++i;
}
} else {
while (i != Q and qs[i].t == t) {
answer[qs[i].queryId] = ar.get(qs[i].i);
++i;
}
}
};
answerQuery(0);
int countShuffle = 0, minPos = N;
for (int v = N; v >= 1; --v) {
if (minPos == N / 2) {
break;
}
const int pos = ar.find(0, v);
if (pos >= N / 2) {
minPos = std::min(minPos, pos);
continue;
}
const int w = minPos - N / 2;
const int dist = N / 2 - pos;
const int c = (dist + w - 1) / w;
for (int gomi = 0; gomi < c; ++gomi) {
int l = 0;
for (int i = N / 2; i < minPos; ++i) {
const int val = ar.get(i);
int p = ar.find(l, val);
if (p >= i) {
p = i;
}
ar.erase(i);
ar.insert(p, val);
l = p + 1;
}
answerQuery(++countShuffle);
ar.debug();
}
minPos = std::min(minPos, ar.find(0, v));
}
answerQuery(-1);
for (const auto e : answer) {
std::cout << e << std::endl;
}
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
// O(N^2)
int N, Q;
std::cin >> N >> Q;
std::vector<int> P(N);
for (auto &e : P) {
std::cin >> e;
}
std::vector<std::pair<i64, int>> queries(Q);
for (auto &[t, i] : queries) {
std::cin >> t >> i;
--i;
}
solve(N, Q, P, queries);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1666 ms |
63356 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3077 ms |
63124 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3041 ms |
11268 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1666 ms |
63356 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
