/* 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 = 24e5+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];
vector<bool> vis(N), pushed(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;
priority_queue<int> Q;
Q.push(d);
coo[d]++;
used.pb(d);
while(!Q.empty()){
int v = Q.top();
Q.pop();
if(v == d_sz) break;
if(vis[v]) continue;
vis[v] = 1;
for(int u: g[v]){
used.pb(u);
coo[u] += coo[v];
if(!pushed[u])
Q.push(u), pushed[u] = 1;
}
}
ll ans = coo[d_sz];
for(auto x: used) vis[x] = pushed[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)
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 << (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;
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:56:49: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
56 | for(auto x: used) vis[x] = pushed[x] = coo[x] = 0;
ogledala.cpp: In function 'void solve()':
ogledala.cpp:93:32: warning: narrowing conversion of 'last' from 'double' to 'long long int' [-Wnarrowing]
93 | if(a[i] - 1 >= last) r.pb({last, a[i] - 1});
| ^~~~
ogledala.cpp:93:43: warning: narrowing conversion of '(a[i] - (double)1)' from 'double' to 'long long int' [-Wnarrowing]
93 | if(a[i] - 1 >= last) r.pb({last, a[i] - 1});
| ~~~~~^~~
ogledala.cpp:96:23: warning: narrowing conversion of 'last' from 'double' to 'long long int' [-Wnarrowing]
96 | if(last <= m) r.pb({last, m});
| ^~~~
ogledala.cpp:96:29: warning: narrowing conversion of 'm' from 'double' to 'long long int' [-Wnarrowing]
96 | if(last <= m) r.pb({last, m});
| ^
ogledala.cpp:107:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
107 | for(int i = 1; i <= al.size(); ++i){
| ~~^~~~~~~~~~~~
ogledala.cpp:140:38: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
140 | for(int x: used) vis[x] = coo[x] = 0;
ogledala.cpp:149:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
149 | for(int i = 1; i <= al.size(); ++i){
| ~~^~~~~~~~~~~~
ogledala.cpp: In function 'int main()':
ogledala.cpp:193:15: warning: unused variable 'aa' [-Wunused-variable]
193 | int tt = 1, aa;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
151632 KB |
Output is correct |
| 2 |
Correct |
29 ms |
151888 KB |
Output is correct |
| 3 |
Correct |
82 ms |
153376 KB |
Output is correct |
| 4 |
Correct |
70 ms |
153592 KB |
Output is correct |
| 5 |
Correct |
97 ms |
159560 KB |
Output is correct |
| 6 |
Correct |
99 ms |
161348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
50 ms |
151888 KB |
Output is correct |
| 2 |
Correct |
49 ms |
151888 KB |
Output is correct |
| 3 |
Correct |
2179 ms |
433128 KB |
Output is correct |
| 4 |
Correct |
2279 ms |
443916 KB |
Output is correct |
| 5 |
Correct |
2761 ms |
505668 KB |
Output is correct |
| 6 |
Correct |
2818 ms |
517872 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1459 ms |
254992 KB |
Output is correct |
| 2 |
Correct |
1469 ms |
253224 KB |
Output is correct |
| 3 |
Correct |
3315 ms |
364248 KB |
Output is correct |
| 4 |
Correct |
3408 ms |
371072 KB |
Output is correct |
| 5 |
Execution timed out |
4045 ms |
505428 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
