#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;
unordered_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){
if(m < 1e10)
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);
}
}
for(auto &u:mp){
points.insert(u.first);
u.second = get_proper(u.second);
reverse(u.second.begin(),u.second.end());
}
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){
| ~~~~~~^~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
30 ms |
2648 KB |
Output is correct |
4 |
Correct |
27 ms |
2988 KB |
Output is correct |
5 |
Correct |
69 ms |
9440 KB |
Output is correct |
6 |
Correct |
71 ms |
11000 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
1408 KB |
Output is correct |
2 |
Correct |
13 ms |
1596 KB |
Output is correct |
3 |
Runtime error |
495 ms |
4504 KB |
Execution killed with signal 11 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
331 ms |
3592 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |