#include <bits/stdc++.h>
#define N 100005
#define K 105
using namespace std;
long long a[N],b[N];
long long len[N];
vector<pair<long long,long long>> get_proper(vector<pair<long long,long long>> a){
vector<pair<long long,long long>> ret;
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;
}
long long val(long long curlen,long long target){
long long ret = 0;
vector<pair<long long,long long>> nums = {{curlen,1}};
while(nums.back().first >= target){
vector<pair<long long,long long>> nw;
for(auto u:nums){
if(u.first == target)ret += u.second;
nw.push_back({(u.first-1)/2,u.second});
nw.push_back({u.first/2,u.second});
}
nums = get_proper(nw);
}
return ret;
}
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>> mp[N * K];
void solve(){
long long m,n,q;
cin >> m >> n >> q;
for(int i = 1;i<=n;i++){
cin >> a[i];
}
a[n+1] = m + 1;
vector<long long> compress;
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){
compress.push_back({u.first});
nw.push_back({(u.first-1)/2,u.second});
nw.push_back({u.first/2,u.second});
}
nums = get_proper(nw);
}
}
sort(compress.begin(),compress.end());
compress.resize(unique(compress.begin(),compress.end()) - compress.begin());
for(int i = 0;i<=n;i++){
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[lower_bound(compress.begin(),compress.end(),u.first) - compress.begin()].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(int i = 0;i<compress.size();i++){
mp[i] = get_proper(mp[i]);
reverse(mp[i].begin(),mp[i].end());
}
int point = compress.size() -1;
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[point].back().second < b[i]){
nowgo += mp[point].back().second;
mp[point].pop_back();
if(mp[point].empty()){
point--;
}
}
b[i] -= nowgo;
cout << get( a[mp[point].back().first] + 1,len[mp[point].back().first],compress[point],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:9: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]
9 | for(int i = 0;i<a.size();i++){
| ~^~~~~~~~~
ogledala.cpp:10: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]
10 | if(i + 1 != a.size() && a[i].first == a[i+1].first){
| ~~~~~~^~~~~~~~~~~
ogledala.cpp: In function 'void solve()':
ogledala.cpp:78:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | for(int i = 0;i<compress.size();i++){
| ~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
116 ms |
246924 KB |
Output is correct |
| 2 |
Correct |
122 ms |
247008 KB |
Output is correct |
| 3 |
Correct |
209 ms |
250252 KB |
Output is correct |
| 4 |
Correct |
174 ms |
250320 KB |
Output is correct |
| 5 |
Correct |
231 ms |
258656 KB |
Output is correct |
| 6 |
Correct |
207 ms |
259972 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
222 ms |
247048 KB |
Output is correct |
| 2 |
Correct |
176 ms |
247180 KB |
Output is correct |
| 3 |
Correct |
3124 ms |
415952 KB |
Output is correct |
| 4 |
Correct |
3298 ms |
421680 KB |
Output is correct |
| 5 |
Correct |
3876 ms |
440572 KB |
Output is correct |
| 6 |
Execution timed out |
4080 ms |
445776 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4069 ms |
344664 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
