/* 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'
#define eps 1e-1
#define ep 1e-6
const int N = 146e4+100, M = 1e5+10, K = 22;
void normal(double &x){
if(abs((double)((long long) x) - x) <= ep) x = (long long) x;
if(abs((double)((long long) x + 1) - x) <= ep) x = (long long) (x + 1);
}
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], par[N];
vector<bool> vis(N);
int compressed(long long 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});
}
long long count_val(int d, int d_sz){
vector<int> used;
int mn = d, mx = d;
coo[d]++;
used.pb(d);
while(mx > 1){
int v = g[mx].back();
if(!vis[v]){
for(int u: par[v])
coo[v] += coo[u];
vis[v] = 1;
used.pb(v);
}
if(mn > 1){
int vv = g[mn][0];
if(!vis[vv]){
for(int u: par[vv]){
coo[vv] += coo[u];
}
vis[vv] = 1;
used.pb(vv);
}
mn = vv;
}
mx = v;
}
ll ans = coo[d_sz];
for(auto x: used) vis[x] = coo[x] = 0;
return ans;
}
long long tree(int d, int d_sz, long long 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){
int u = compressed(((al[i - 1] + 1) >> 1) - 1);
g[i].pb(u);
par[u].pb(i);
}
int u = compressed(al[i - 1] >> 1);
g[i].pb(u);
par[u].pb(i);
}
}
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*/
int llast = al.size();
for(;q--;){
ll b; cin >> b;
if(b <= n){
cout << (long long) 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;
for(int j = sz + 1; j <= llast; ++j) coi[j].clear();
llast = sz;
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] + (long long)(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:64:37: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
64 | for(auto x: used) vis[x] = coo[x] = 0;
ogledala.cpp: In function 'void solve()':
ogledala.cpp:101:32: warning: narrowing conversion of 'last' from 'double' to 'long long int' [-Wnarrowing]
101 | if(a[i] - 1 >= last) r.pb({last, a[i] - 1});
| ^~~~
ogledala.cpp:101:43: warning: narrowing conversion of '(a[i] - (double)1)' from 'double' to 'long long int' [-Wnarrowing]
101 | if(a[i] - 1 >= last) r.pb({last, a[i] - 1});
| ~~~~~^~~
ogledala.cpp:104:23: warning: narrowing conversion of 'last' from 'double' to 'long long int' [-Wnarrowing]
104 | if(last <= m) r.pb({last, m});
| ^~~~
ogledala.cpp:104:29: warning: narrowing conversion of 'm' from 'double' to 'long long int' [-Wnarrowing]
104 | if(last <= m) r.pb({last, m});
| ^
ogledala.cpp:115:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
115 | for(int i = 1; i <= al.size(); ++i){
| ~~^~~~~~~~~~~~
ogledala.cpp:153:38: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
153 | for(int x: used) vis[x] = coo[x] = 0;
ogledala.cpp:162:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
162 | for(int i = 1; i <= al.size(); ++i){
| ~~^~~~~~~~~~~~
ogledala.cpp: In function 'int main()':
ogledala.cpp:209:15: warning: unused variable 'aa' [-Wunused-variable]
209 | int tt = 1, aa;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
126296 KB |
Output is correct |
| 2 |
Correct |
25 ms |
126296 KB |
Output is correct |
| 3 |
Correct |
69 ms |
128076 KB |
Output is correct |
| 4 |
Correct |
66 ms |
128332 KB |
Output is correct |
| 5 |
Correct |
95 ms |
134728 KB |
Output is correct |
| 6 |
Correct |
100 ms |
137416 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
49 ms |
126800 KB |
Output is correct |
| 2 |
Correct |
47 ms |
126908 KB |
Output is correct |
| 3 |
Runtime error |
3235 ms |
524288 KB |
Execution killed with signal 9 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1125 ms |
233040 KB |
Output is correct |
| 2 |
Correct |
1124 ms |
232060 KB |
Output is correct |
| 3 |
Correct |
2681 ms |
364340 KB |
Output is correct |
| 4 |
Correct |
2844 ms |
375188 KB |
Output is correct |
| 5 |
Runtime error |
3259 ms |
524288 KB |
Execution killed with signal 9 |
| 6 |
Halted |
0 ms |
0 KB |
- |
