#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;
}
pair<pair<long long,long long>,pair<long long,long long>> get(pair<pair<long long,long long>,pair<long long,long long>> nums){
pair<pair<long long,long long>,pair<long long,long long>> nw = {{-1,-1},{-1,-1}};
if(nums.second.first == -1){
if(nums.first.first & 1){
nw.first = {nums.first.first/2,2*nums.first.second};
}
else{
nw.first = {nums.first.first/2,nums.first.second};
nw.second = {nums.first.first/2 - 1,nums.first.second};
}
}
else{
if(nums.first.first & 1){
nw.first = {nums.first.first/2,2*nums.first.second + nums.second.second};
nw.second = {nums.first.first/2 - 1,nums.second.second};
}
else{
nw.first = {nums.first.first/2,nums.first.second};
nw.second = {nums.first.first/2 - 1,nums.first.second + 2*nums.second.second};
}
}
return nw;
}
long long val(long long curlen,long long target){
long long ret = 0;
pair<pair<long long,long long>,pair<long long,long long>> nums = {{curlen,1},{-1,-1}};
while(nums.first.first >= target){
if(nums.first.first == target)ret += nums.first.second;
if(nums.second.first == target)ret += nums.second.second;
nums = get(nums);
}
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:97:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
97 | for(int i = 0;i<compress.size();i++){
| ~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
112 ms |
246820 KB |
Output is correct |
| 2 |
Correct |
110 ms |
246828 KB |
Output is correct |
| 3 |
Correct |
139 ms |
250180 KB |
Output is correct |
| 4 |
Correct |
136 ms |
250388 KB |
Output is correct |
| 5 |
Correct |
196 ms |
258504 KB |
Output is correct |
| 6 |
Correct |
192 ms |
259920 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
116 ms |
247168 KB |
Output is correct |
| 2 |
Correct |
113 ms |
247176 KB |
Output is correct |
| 3 |
Correct |
3006 ms |
415980 KB |
Output is correct |
| 4 |
Correct |
3164 ms |
421600 KB |
Output is correct |
| 5 |
Correct |
3713 ms |
440424 KB |
Output is correct |
| 6 |
Correct |
3857 ms |
445960 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1574 ms |
344816 KB |
Output is correct |
| 2 |
Correct |
1419 ms |
351112 KB |
Output is correct |
| 3 |
Correct |
2773 ms |
390248 KB |
Output is correct |
| 4 |
Correct |
2700 ms |
393752 KB |
Output is correct |
| 5 |
Execution timed out |
4077 ms |
441764 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
