/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
#define ll double
#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[M];
vector<pair<ll, int>> pref, coi[N];
vector<array<long long, 2>> r;
vector<long long> al, coo(N), co(N);
vector<int> g[N];
vector<bool> vis(N);
int compressed(ll sz){
return (lower_bound(all(al), sz) - al.begin() + 1);
}
/*add something to somewheres prefix*/
void add(int x, ll val, int pos){
coi[x].pb({(coi[x].empty() ? 0 : coi[x].back().first) + val, pos});
}
ll count_val(int d, int d_sz){
vector<int> used;
set<int> Q;
Q.insert(d);
coo[d]++;
while(!Q.empty()){
auto it = prev(Q.end());
int v = *it;
Q.erase(it);
if(vis[v]) continue;
vis[v] = 1;
used.pb(v);
for(int u: g[v]){
coo[u] += coo[v];
Q.insert(u);
}
}
ll ans = coo[d_sz];
for(auto x: used) vis[x] = coo[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 2;
}
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 proc(long long len){
long long mn = len, mx = len;
while(mx > 0){
if(mn > 0) al.pb(mn);
if(mx > 0) al.pb(mx);
mx >>= 1;
if(mn & 1) mn >>= 1;
else mn = (mn>>1) - 1;
}
}
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){
proc(x[1] - x[0] + 1);
}
/* compressed tree */
sort(all(al));
al.erase(unique(all(al)), al.end());
// assert(al.size() < N);
for(int i = 1; i <= al.size(); ++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));
}
}
for(auto x: r){
int v = compressed(x[1] - x[0] + 1);
set<int> Q;
vector<int> used;
Q.insert(v);
coo[v]++;
while(!Q.empty()){
auto it = prev(Q.end());
int v = *it;
Q.erase(it);
if(vis[v]) continue;
add(v, coo[v], rn);
co[v] += coo[v];
used.pb(v);
vis[v] = 1;
for(int u: g[v]){
coo[u] += coo[v];
Q.insert(u);
}
}
for(int x: used) vis[x] = coo[x] = 0;
++rn;
}
/* prefix build */
vector<pair<ll, ll>> vv;
for(int i = 1; i <= al.size(); ++i){
vv.pb({i, co[i]});
}
reverse(all(vv));
pref.pb({0ll, 0});
for(auto p: vv){
pref.pb({p.second + pref.back().first, p.first});
}
// 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[int(b)] << '\n';
continue;
}
b -= n;
int sz_pos = lower_bound(all(pref), pair<ll, int>{b, 0}) - pref.begin();
int sz = pref[sz_pos].second;
b -= pref[sz_pos - 1].first;
// assert(!coi[sz].empty());
int pos = upper_bound(all(coi[sz]), pair<ll, int>{b, 0}) - coi[sz].begin();
--pos;
// assert(pos >= 0);
if(pos >= 0)
b -= coi[sz][pos].first;
int pos_a = coi[sz][pos + 1].second;
// assert(pos_a <= n);
// 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), 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 'double count_val(int, int)':
ogledala.cpp:47:37: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
47 | for(auto x: used) vis[x] = coo[x] = 0;
ogledala.cpp: In function 'void solve()':
ogledala.cpp:83:32: warning: narrowing conversion of 'last' from 'double' to 'long long int' [-Wnarrowing]
83 | if(a[i] - 1 >= last) r.pb({last, a[i] - 1});
| ^~~~
ogledala.cpp:83:43: warning: narrowing conversion of '(a[i] - (double)1)' from 'double' to 'long long int' [-Wnarrowing]
83 | if(a[i] - 1 >= last) r.pb({last, a[i] - 1});
| ~~~~~^~~
ogledala.cpp:86:23: warning: narrowing conversion of 'last' from 'double' to 'long long int' [-Wnarrowing]
86 | if(last <= m) r.pb({last, m});
| ^~~~
ogledala.cpp:86:29: warning: narrowing conversion of 'm' from 'double' to 'long long int' [-Wnarrowing]
86 | if(last <= m) r.pb({last, m});
| ^
ogledala.cpp:97:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
97 | for(int i = 1; i <= al.size(); ++i){
| ~~^~~~~~~~~~~~
ogledala.cpp:130:38: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
130 | for(int x: used) vis[x] = coo[x] = 0;
ogledala.cpp:139:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
139 | for(int i = 1; i <= al.size(); ++i){
| ~~^~~~~~~~~~~~
ogledala.cpp: In function 'int main()':
ogledala.cpp:183:15: warning: unused variable 'aa' [-Wunused-variable]
183 | int tt = 1, aa;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
62 ms |
314196 KB |
Output is correct |
| 2 |
Correct |
60 ms |
314192 KB |
Output is correct |
| 3 |
Correct |
156 ms |
316012 KB |
Output is correct |
| 4 |
Correct |
143 ms |
316240 KB |
Output is correct |
| 5 |
Correct |
171 ms |
322364 KB |
Output is correct |
| 6 |
Correct |
174 ms |
324164 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
147 ms |
314592 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2123 ms |
416636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
