#include <bits/stdc++.h>
#define N 100005
using namespace std;
long long a[N],b[N];
long long len[N];
map<pair<long long,long long>,long long> rem;
long long val(long long curlen,long long target){
if(curlen <= target)return curlen == target;
if(rem.count({curlen,target}))
return rem[{curlen,target}];
return rem[{curlen,target}] = val((curlen-1)/2,target) + val(curlen/2,target);
}
long long get(long long st,long long curlen,long long target,long long idx){
if(curlen == target)return st + (target - 1)/2;
long long nwlen = (curlen - 1)/2;
if(val(nwlen,target) >= idx){
return get(st,nwlen,target,idx);
}
idx -= val(nwlen,target);
nwlen = (curlen)/2;
return get(st + (curlen + 1)/2,nwlen,target,idx);
}
vector<pair<long long,long long>> get_proper(vector<pair<long long,long long>> a){
vector<pair<long long,long long>> ret;
if(!is_sorted(a.begin(),a.end()))
sort(a.begin(),a.end());
for(int i = 0;i<a.size();i++){
if(i + 1 != a.size() && a[i].first == a[i+1].first){
a[i+1].second += a[i].second;
continue;
}
ret.push_back(a[i]);
}
return ret;
}
void solve(){
long long m,n,q;
cin >> m >> n >> q;
map<long long,vector<pair<long long,long long>>> mp;
set<long long> points;
for(int i = 1;i<=n;i++){
cin >> a[i];
}
a[n+1] = m + 1;
for(int i = 0;i<=n;i++){
len[i] = a[i+1] - a[i] - 1;
vector<pair<long long,long long>> nums = {{len[i],1}};
while(nums.back().first > 0){
vector<pair<long long,long long>> nw;
for(auto u:nums){
mp[u.first].push_back({i,u.second});
nw.push_back({(u.first-1)/2,u.second});
nw.push_back({u.first/2,u.second});
}
nums = get_proper(nw);
}
/*
map<long long,long long> cnt;
cnt[len[i]] = 1;
set<long long> nums = {len[i]};
while(*nums.rbegin() > 0){
long long nowlen = *nums.rbegin();
nums.erase(nowlen);
points.insert(nowlen);
mp[nowlen].push_back({i,cnt[nowlen]});
nums.insert((nowlen-1)/2);
nums.insert(nowlen/2);
cnt[(nowlen-1)/2] += cnt[nowlen];
cnt[nowlen/2] += cnt[nowlen];
}*/
}
for(auto &u:mp){
points.insert(u.first);
u.second = get_proper(u.second);
reverse(u.second.begin(),u.second.end());
}
if(m > 1e10)return;
long long nowgo = n;
for(int i = 1;i<=q;i++){
cin >> b[i];
if(b[i] <= n){
cout << a[b[i]] << "\n";
continue;
}
while(nowgo + mp[*points.rbegin()].back().second < b[i]){
nowgo += mp[*points.rbegin()].back().second;
mp[*points.rbegin()].pop_back();
if(mp[*points.rbegin()].empty()){
points.erase(*points.rbegin());
}
}
b[i] -= nowgo;
cout << get( a[mp[*points.rbegin()].back().first] + 1,len[mp[*points.rbegin()].back().first],*points.rbegin(),b[i]) << "\n";
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef Local
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int t = 1;
//cin >> t;
while(t--){
solve();
}
#ifdef Local
cout << endl << fixed << setprecision(2) << 1000.0*clock()/CLOCKS_PER_SEC << " milliseconds.";
#endif
}
Compilation message
ogledala.cpp: In function 'std::vector<std::pair<long long int, long long int> > get_proper(std::vector<std::pair<long long int, long long int> >)':
ogledala.cpp:28:20: 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]
28 | for(int i = 0;i<a.size();i++){
| ~^~~~~~~~~
ogledala.cpp:29: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]
29 | if(i + 1 != a.size() && a[i].first == a[i+1].first){
| ~~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
31 ms |
2872 KB |
Output is correct |
| 4 |
Correct |
27 ms |
2904 KB |
Output is correct |
| 5 |
Correct |
68 ms |
9748 KB |
Output is correct |
| 6 |
Correct |
64 ms |
11452 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
1352 KB |
Output is correct |
| 2 |
Correct |
20 ms |
1540 KB |
Output is correct |
| 3 |
Incorrect |
3367 ms |
312048 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2096 ms |
98440 KB |
Output is correct |
| 2 |
Correct |
2201 ms |
99300 KB |
Output is correct |
| 3 |
Incorrect |
2501 ms |
215268 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
