#define fast ios::sync_with_stdio(false); cin.tie(0)
#define foru(i, k, n) for (int i = k; i < n; i++)
#define ford(i, k, n) for (int i = k; i >= n; i--)
#define pb push_back
#define ff first
#define ss second
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int sz = 1e5 + 5;
ll m, n, q;
ll a[sz], b[sz];
int segsSize, lensSize;
vector<pll> segs;
vector<pair<pll, ll>> lensAll; //len, -idx, amt
vector<pll> lens[sz];
void input() {
cin >> m >> n >> q;
foru(i, 0, n) {
cin >> a[i]; a[i]--;
}
foru(i, 0, q) {
cin >> b[i]; b[i]--;
}
if (a[0] != 0)segs.pb({ a[0],-1 });
foru(i, 0, n - 1) {
if (a[i + 1] - a[i] != 1)segs.pb({ a[i + 1] - a[i] - 1,i });
}
if (a[n - 1] != m - 1)segs.pb({ m - 1 - a[n - 1],n - 1 });
segsSize = segs.size();
}
void interpretSegs() {
map<ll, ll, greater<ll>> mem;
foru(idx, 0, segsSize) {
mem[segs[idx].ff] = 1;
while (!mem.empty()) {
pll x = *mem.begin(); mem.erase(x.first);
lens[idx].pb(x);
lensAll.pb({ {x.ff, -idx},x.ss });
ll amt = x.ff;
if (amt & 1) {
if (amt != 1)mem[amt >> 1] += (x.ss * 2);
}
else {
mem[amt >> 1] += x.ss;
if (amt != 2)mem[(amt >> 1) - 1] += x.ss;
}
}
}
}
ll countSegAmount(ll initialLen, ll val) {
if (initialLen <= val)return (initialLen == val);
unordered_map<ll, ll> mem, mem2;
mem[initialLen] = 1;
ll ret = 0;
while (!mem.empty()) {
for (pll x : mem) {
if (x.ff == val)ret += x.ss;
else if (x.ff > val) {
mem2[x.ff >> 1] += x.ss;
mem2[(x.ff - 1) >> 1] += x.ss;
}
}
mem = mem2;
mem2.clear();
}
return ret;
}
ll findIndex(ll serialNum, ll val, ll lseg, ll rseg) {
ll len = rseg - lseg + 1, mid = (lseg + rseg) / 2;
if (len == val)return mid;
ll cntLeft = countSegAmount((len - 1) / 2, val);
if (cntLeft >= serialNum) return findIndex(serialNum, val, lseg, mid - 1);
else return findIndex(serialNum - cntLeft, val, mid + 1, rseg);
}
pll findLR(int id) {
int aid = segs[id].ss;
if (aid == -1)return { 0,a[0] - 1 };
else if (aid == n - 1)return { a[aid] + 1,m - 1 };
else return { a[aid] + 1,a[aid + 1] - 1 };
}
int main() {
fast;
input();
interpretSegs();
sort(lensAll.begin(), lensAll.end(), greater<pair<pll, ll>>());
lensSize = lensAll.size();
int qid = 0, lenid = 0;
ll crid = n;
while (qid < q) {
if (b[qid] < n)cout << a[b[qid++]] + 1 << '\n';
else {
while (crid <= b[qid] && lenid < lensSize) {
if (crid + lensAll[lenid].ss <= b[qid]) crid += lensAll[lenid++].ss;
else {
pll fs = findLR(-lensAll[lenid].ff.ss);
cout << findIndex(b[qid++] - crid + 1, lensAll[lenid].ff.ff, fs.ff, fs.ss) + 1 << '\n';
break;
}
}
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2668 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2668 KB |
Output is correct |
| 3 |
Correct |
78 ms |
6568 KB |
Output is correct |
| 4 |
Correct |
52 ms |
6560 KB |
Output is correct |
| 5 |
Correct |
75 ms |
16096 KB |
Output is correct |
| 6 |
Correct |
73 ms |
16372 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
56 ms |
3180 KB |
Output is correct |
| 2 |
Correct |
51 ms |
3180 KB |
Output is correct |
| 3 |
Correct |
1264 ms |
292116 KB |
Output is correct |
| 4 |
Correct |
1272 ms |
289684 KB |
Output is correct |
| 5 |
Correct |
1400 ms |
281876 KB |
Output is correct |
| 6 |
Correct |
1422 ms |
280084 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2746 ms |
150264 KB |
Output is correct |
| 2 |
Correct |
2653 ms |
146424 KB |
Output is correct |
| 3 |
Execution timed out |
4080 ms |
305300 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
