/* 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 = 1e6+100, M = 1e5+10, K = 22;
ll m, n, q, a[N];
vector<tuple<ll, int>> pref, coi[N];
vector<array<ll, 2>> r;
map<ll, int> compressed;
vector<ll> al, coo(N), co(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({get<0>(coi[x].back()) + val, pos});
}
ll count_val(int d, int d_sz){
vector<int> used;
priority_queue<int> Q;
Q.push(d);
coo[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]){
coo[u] += coo[v];
Q.push(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(ll len){
ll 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){
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]);
}
}
for(auto x: r){
int v = compressed[x[1] - x[0] + 1];
priority_queue<int> Q;
vector<int> used;
Q.push(v);
coo[v]++;
while(!Q.empty()){
int v = Q.top();
Q.pop();
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.push(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 + get<0>(pref.back()), 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[b] << '\n';
continue;
}
b -= n;
int sz_pos = lower_bound(all(pref), tuple<ll, int>{b, 0}) - pref.begin();
ll sz = get<1>(pref[sz_pos]);
b -= get<0>(pref[sz_pos - 1]);
// assert(!coi[sz].empty());
int pos = upper_bound(all(coi[sz]), tuple<ll, int>{b, 0}) - coi[sz].begin();
--pos;
// assert(pos >= 0);
b -= get<0>(coi[sz][pos]);
int pos_a = get<1>(coi[sz][pos + 1]);
// 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 'long long int count_val(int, int)':
ogledala.cpp:44:37: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
44 | for(auto x: used) vis[x] = coo[x] = 0;
ogledala.cpp: In function 'void solve()':
ogledala.cpp:94:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | for(int i = 1; i <= al.size(); ++i){
| ~~^~~~~~~~~~~~
ogledala.cpp:127:38: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
127 | for(int x: used) vis[x] = coo[x] = 0;
ogledala.cpp:136:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
136 | for(int i = 1; i <= al.size(); ++i){
| ~~^~~~~~~~~~~~
ogledala.cpp: In function 'int main()':
ogledala.cpp:179:15: warning: unused variable 'aa' [-Wunused-variable]
179 | int tt = 1, aa;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
63576 KB |
Output is correct |
| 2 |
Correct |
13 ms |
63576 KB |
Output is correct |
| 3 |
Correct |
67 ms |
65460 KB |
Output is correct |
| 4 |
Correct |
47 ms |
65612 KB |
Output is correct |
| 5 |
Correct |
67 ms |
73020 KB |
Output is correct |
| 6 |
Correct |
57 ms |
73788 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
65 ms |
64088 KB |
Output is correct |
| 2 |
Correct |
60 ms |
64088 KB |
Output is correct |
| 3 |
Runtime error |
925 ms |
408716 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1652 ms |
179516 KB |
Output is correct |
| 2 |
Correct |
1630 ms |
178196 KB |
Output is correct |
| 3 |
Correct |
3940 ms |
352200 KB |
Output is correct |
| 4 |
Runtime error |
879 ms |
406124 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
