/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
const int N = 5e6+100, M = 1e5+10, K = 22;
ll m, n, q, a[N];
vector<array<ll, 2>> r, pref;
map<ll, ll> co;
map<ll, vector<array<ll, 2>>> coi;
map<ll, int> compressed;
vector<ll> al, co_vector(N);
vector<int> g[N];
vector<bool> vis(N);
/*add something to somewheres prefix*/
void add(ll x, ll val, ll pos){
if(coi[x].empty()) coi[x].pb({0, 0});
coi[x].pb({coi[x].back()[0] + val, pos});
}
ll count_val(int d, int d_sz){
vector<int> used;
priority_queue<int> Q;
Q.push(d);
co_vector[d]++;
while(!Q.empty()){
int v = Q.top();
Q.pop();
if(vis[v]) continue;
vis[v] = 1;
used.pb(v);
for(int u: g[v]){
co_vector[u] += co_vector[v];
Q.push(u);
}
}
ll ans = co_vector[d_sz];
for(auto x: used) vis[x] = co_vector[x] = 0;
return ans;
}
ll tree(int d, int d_sz, ll pos){
// cout << d << ' ' << pos << 'g' << '\n';
if(d == d_sz) return (al[d - 1] + 1) >> 1;
if(g[d].size() == 1){
return 1 + tree(g[d][0], d_sz, pos);
}
ll coval = count_val(g[d][0], d_sz);
// cout << coval << ' ' << d << 'f' << pos << endl;
if(coval >= pos)
return tree(g[d][0], d_sz, pos);
pos -= coval;
return al[g[d][0] - 1] + 1 + tree(g[d][1], d_sz, pos);
}
void solve(){
cin >> m >> n >> q;
ll last = 1;
for(int i = 1; i <= n; ++i){
cin >> a[i];
if(a[i] - 1 >= last) r.pb({last, a[i] - 1});
last = a[i] + 1;
}
if(last < m) r.pb({last, m});
int rn = 1;
for(auto x: r){
priority_queue<ll> Q;
map<ll, bool> vis;
map<ll, ll> coo;
Q.push(x[1] - x[0] + 1);
coo[x[1] - x[0] + 1]++;
while(!Q.empty()){
ll v = Q.top();
al.pb(v);
Q.pop();
if(vis[v]) continue;
add(v, coo[v], rn);
co[v] += coo[v];
// cout << v << ' ' << co[v] << ' ' << coo[v] << ' ' << rn << '\n';
vis[v] = 1;
if(v & 1){
if(v > 1){
coo[v >> 1] += coo[v] * 2;
Q.push(v >> 1);
}
}else{
coo[v >> 1] += coo[v];
Q.push(v >> 1);
if(v > 2){
coo[(v >> 1) - 1] += coo[v];
Q.push((v >> 1) - 1);
}
}
}
++rn;
}
/* compressed tree */
sort(all(al));
al.erase(unique(all(al)), al.end());
for(int i = 1; i <= al.size(); ++i){
compressed[al[i - 1]] = i;
if(al[i - 1] > 1){
if(al[i - 1] > 2)
g[i].pb(compressed[((al[i - 1] + 1) >> 1) - 1]);
g[i].pb(compressed[al[i - 1] >> 1]);
}
}
/* prefix build */
vector<pair<ll, ll>> vv;
for(auto p: co){
vv.pb(p);
}
reverse(all(vv));
pref.pb({0ll, 0ll});
for(auto p: vv){
pref.pb({p.second + pref.back()[0], p.first});
// cout << pref.back()[0] << ' ' << pref.back()[1] << '\n';
}
// en;
// for(auto x: coi){
// cout << x.first << ':';
// for(auto y: x.second) cout << y[0] << ' ' << y[1] << '\n';
// en;
// }
/* queries*/
for(;q--;){
ll b; cin >> b;
if(b <= n){
cout << a[b] << '\n';
continue;
}
b -= n;
int sz_pos = lower_bound(all(pref), array<ll, 2>{b, 0ll}) - pref.begin();
ll sz = pref[sz_pos][1];
b -= pref[sz_pos - 1][0];
int pos = upper_bound(all(coi[sz]), array<ll, 2>{b, 0ll}) - coi[sz].begin();
--pos;
b -= coi[sz][pos][0];
int pos_a = coi[sz][pos + 1][1];
// cout << pos_a << '\n';
// cout << r[pos_a - 1][1] - r[pos_a - 1][0] + 1 << ' ' << sz << ' ' << b << '\n';
// cout << r[pos_a-1][0] << ' ' << r[pos_a-1][1] << ' ' << sz << ' ' << b << '\n';
cout << r[pos_a - 1][0] + tree(compressed[r[pos_a - 1][1] - r[pos_a - 1][0] + 1], compressed[sz], b) - 1 << '\n';
}
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
int tt = 1, aa;
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
while(tt--){
solve();
}
cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
return 0;
}
Compilation message
ogledala.cpp: In function 'long long int count_val(int, int)':
ogledala.cpp:45:43: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
45 | for(auto x: used) vis[x] = co_vector[x] = 0;
ogledala.cpp: In function 'void solve()':
ogledala.cpp:116:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
116 | for(int i = 1; i <= al.size(); ++i){
| ~~^~~~~~~~~~~~
ogledala.cpp: In function 'int main()':
ogledala.cpp:170:15: warning: unused variable 'aa' [-Wunused-variable]
170 | int tt = 1, aa;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
159312 KB |
Output is correct |
| 2 |
Correct |
30 ms |
159360 KB |
Output is correct |
| 3 |
Runtime error |
196 ms |
326488 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
80 ms |
160392 KB |
Output is correct |
| 2 |
Correct |
78 ms |
160340 KB |
Output is correct |
| 3 |
Execution timed out |
4061 ms |
486800 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3087 ms |
306792 KB |
Output is correct |
| 2 |
Correct |
3036 ms |
309420 KB |
Output is correct |
| 3 |
Execution timed out |
4045 ms |
441920 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
