#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
long long mid = 1;
map<long long,long long> dp;
long long lim = 1e18;
long long solve(long long x){
if(x<mid)return 0;
if(dp.find(x)!=dp.end())return dp[x];
return dp[x]=(x<=lim?1LL:0LL)+solve(x/2)+solve((x-1)/2);
}
long long ge(long long l,long long r,long long x){
if(x==1&&r-l+1==mid){
return (l+r)/2;
}
long long len = r-l+1;
if(solve((len-1)/2)>=x){
return ge(l,l+((len-1)/2)-1,x);
}else{
return ge(l+((len+1)/2),r,x-solve((len-1)/2));
}
}
signed main() {
ios_base::sync_with_stdio(0);cin.tie(0);
long long m,n,q;
cin>>m>>n>>q;
long long arr[n+2];
arr[0] = 0;
for(int i = 1;i<=n;i++){
cin>>arr[i];
}
arr[n+1] = m+1;
vector<pair<long long,long long>> v[n+1];
vector<pair<long long,long long>> all;
map<long long,vector<pair<long long,long long>>> le;
for(int i = 0;i<=n;i++){
dp.clear();
long long x = solve(arr[i+1]-arr[i]-1);
vector<long long> elem;
for(auto i:dp){
elem.push_back(i.first);
}
//cout<<"hh"<<endl;
v[i].push_back({elem[elem.size()-1],1});
//cout<<elem.size()<<"sz"<<endl;
//cout<<elem[elem.size()-1]<<"elem"<<endl;
for(int j = elem.size()-2;j>=0;j--){
//cout<<elem[j]<<"elem"<<endl;
long long sum = 0;
for(int e = 0;e<=2;e++){
int ind = lower_bound(elem.begin(),elem.end(),elem[j]*2+e)-elem.begin();
//cout<<ind<<"ind"<<endl;
if(ind==elem.size())continue;
if(elem[ind]!=elem[j]*2+e)continue;
//cout<<ind<<"ind"<<endl;
long long rev = elem.size()-1-ind;
sum+=((e==1)+1)*v[i][rev].second;
//cout<<"xd"<<endl;
}
v[i].push_back({elem[j],sum});
}
reverse(v[i].begin(),v[i].end());
all.push_back(v[i][v[i].size()-1]);
le[v[i][v[i].size()-1].first].push_back({v[i][v[i].size()-1].second,i});
for(int j = v[i].size()-2;j>=0;j--){
all.push_back(v[i][j]);
le[v[i][j].first].push_back({v[i][j].second,i});
v[i][j].second+=v[i][j+1].second;
}
}
for(auto i:le){
for(int j = 1;j<i.second.size();j++){
le[i.first][j].first+=le[i.first][j-1].first;
}
}
sort(all.begin(),all.end());
for(int i = all.size()-2;i>=0;i--){
all[i].second+=all[i+1].second;
}
while(q--){
long long x;cin>>x;
if(x<=n){
cout<<arr[x]<<endl;
continue;
}
x-=n;
long long l=1,r=1e9 , ans = 0;
while(l<=r){
mid = (l+r)/2;
int it = lower_bound(all.begin(),all.end(),make_pair(mid,0LL))-all.begin();
long long al =0;
if(it<all.size())al = all[it].second;
if(al>=x){
ans = mid;
l = mid+1;
}else r = mid-1;
}
//cout<<ans<<"anss"<<endl;
int it = lower_bound(all.begin(),all.end(),make_pair(ans+1,0LL))-all.begin();
long long al =0;
if(it<all.size())al = all[it].second;
x-=al;
dp.clear();
mid = ans;
lim = ans;
it = lower_bound(le[ans].begin(),le[ans].end(),make_pair(x,0LL))-le[ans].begin();
if(it)x-=le[ans][it-1].first;
it = le[ans][it].second;
//cout<<arr[it]<<endl;
dp.clear();
cout<<ge(arr[it]+1,arr[it+1]-1,x)<<endl;
}
return 0;
}
Compilation message
ogledala.cpp: In function 'int main()':
ogledala.cpp:54:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | if(ind==elem.size())continue;
| ~~~^~~~~~~~~~~~~
ogledala.cpp:39:19: warning: unused variable 'x' [-Wunused-variable]
39 | long long x = solve(arr[i+1]-arr[i]-1);
| ^
ogledala.cpp:73:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | for(int j = 1;j<i.second.size();j++){
| ~^~~~~~~~~~~~~~~~
ogledala.cpp:93:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | if(it<all.size())al = all[it].second;
| ~~^~~~~~~~~~~
ogledala.cpp:102:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
102 | if(it<all.size())al = all[it].second;
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
456 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
852 KB |
Output is correct |
| 2 |
Correct |
18 ms |
980 KB |
Output is correct |
| 3 |
Runtime error |
3663 ms |
524288 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
480 ms |
172636 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
