#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
#define fi first
#define se second
const int maxN = 1e5 + 5;
const ll INF = 1e18;
ll M, N, Q;
ll A[maxN], B[maxN];
struct Segment {
ll len, cnt, initPos;
Segment(ll len, ll cnt, ll initPos) :
len(len), cnt(cnt), initPos(initPos)
{}
bool operator < (const Segment &other) const {
return make_pair(-len, initPos) < make_pair(-other.len, other.initPos);
}
};
void split(ll len, vector<pll> &V) {
if (len == 0) return;
// all possible lengths can form pairs of {p, p-1}
V.push_back({len+1, 0});
V.push_back({len, 1});
for (ll ptr = 0; ; ptr += 2) {
ll big = V[ptr].fi / 2;
ll small = (V[ptr+1].fi - 1) / 2;
//cout << V[ptr].fi << ' ' << V[ptr].se << '\n';
//cout << V[ptr+1].fi << ' ' << V[ptr+1].se << '\n';
ll Bcnt = V[ptr].se, Scnt = V[ptr+1].se;
if ((V[ptr].fi - 1) / 2 == big) {
Bcnt += V[ptr].se;
} else {
Scnt += V[ptr].se;
}
if (V[ptr+1].fi / 2 == big) {
Bcnt += V[ptr+1].se;
} else {
Scnt += V[ptr+1].se;
}
V.push_back({big, Bcnt});
V.push_back({small, Scnt});
if (big == 0 && small == 0) break;
}
while (!V.empty() && (!V.back().fi || !V.back().se)) V.pop_back();
ll one = 0;
while (!V.empty() && (V.back().fi == 1)) {
one += V.back().se;
V.pop_back();
}
if (one) V.push_back({1, one});
//for (auto &[len, cnt] : V) {cout << len << ' ' << cnt << '\n';}
}
ll findPos(ll findLen, ll l, ll r, ll val) {
//cerr << "findPos(" << findLen << ", " << l << ", " << r << ", " << val << ")\n";
if (r - l + 1 == findLen) {return l + (r-l)/2;}
vector<pll> tmp;
ll m = l + (r-l)/2;
split(m-l, tmp);
ll findCnt = 0;
for (auto &[len, cnt] : tmp) {
if (len == findLen) {findCnt += cnt; break;}
}
//cerr << findCnt << '\n';
if (val <= findCnt) {
return findPos(findLen, l, m-1, val);
} else {
return findPos(findLen, m+1, r, val-findCnt);
}
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> M >> N >> Q;
A[0] = 0, A[N+1] = M+1;
for (ll i = 1; i <= N; i++) {
cin >> A[i];
}
vector<Segment> S;
for (ll i = 1; i <= N+1; i++) {
vector<pll> tmp;
split(A[i] - A[i-1] - 1, tmp);
for (auto &[len, cnt] : tmp) {
if (len && cnt) S.push_back(Segment(len, cnt, i));
}
}
sort(S.begin(), S.end());
for (auto &[len, cnt, idx] : S) {
//cerr << len << ' ' << cnt << ' ' << idx << '\n';
}
for (ll i = 1; i <= Q; i++) {
cin >> B[i];
}
B[Q+1] = INF;
ll qptr = 1;
for (; B[qptr] <= N; qptr++) {
cout << A[B[qptr]] << '\n';
}
ll cur = N+1;
for (auto &[len, cnt, idx] : S) {
//cout << "! " << cur << '\n';
for (; B[qptr] <= cur + cnt - 1; qptr++) {
cout << findPos(len, A[idx-1]+1, A[idx]-1, B[qptr] - cur + 1) << '\n';
}
cur += cnt;
}
}
Compilation message
ogledala.cpp: In function 'int main()':
ogledala.cpp:110:13: warning: unused structured binding declaration [-Wunused-variable]
110 | for (auto &[len, cnt, idx] : S) {
| ^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
49 ms |
2392 KB |
Output is correct |
| 4 |
Correct |
37 ms |
2544 KB |
Output is correct |
| 5 |
Correct |
56 ms |
7300 KB |
Output is correct |
| 6 |
Correct |
67 ms |
7384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
672 KB |
Output is correct |
| 2 |
Correct |
29 ms |
640 KB |
Output is correct |
| 3 |
Correct |
891 ms |
198208 KB |
Output is correct |
| 4 |
Correct |
886 ms |
199780 KB |
Output is correct |
| 5 |
Correct |
997 ms |
199776 KB |
Output is correct |
| 6 |
Correct |
1004 ms |
199784 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1086 ms |
99732 KB |
Output is correct |
| 2 |
Correct |
1038 ms |
100944 KB |
Output is correct |
| 3 |
Correct |
1735 ms |
199652 KB |
Output is correct |
| 4 |
Correct |
1727 ms |
199844 KB |
Output is correct |
| 5 |
Correct |
2574 ms |
199800 KB |
Output is correct |
| 6 |
Correct |
2521 ms |
199856 KB |
Output is correct |
