#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;
pair<pair<long long,long long>,pair<long long,long long>> nums = {{len[i],1},{-1,-1}};
while(nums.first.first >= 1){
if(nums.first.first != -1)compress.push_back(nums.first.first);
if(nums.second.first != -1)compress.push_back(nums.second.first);
nums = get(nums);
}
}
sort(compress.begin(),compress.end());
compress.resize(unique(compress.begin(),compress.end()) - compress.begin());
for(int i = 0;i<=n;i++){
pair<pair<long long,long long>,pair<long long,long long>> nums = {{len[i],1},{-1,-1}};
while(nums.first.first >= 1){
if(nums.first.first != -1)mp[lower_bound(compress.begin(),compress.end(),nums.first.first) - compress.begin()].push_back({i,nums.first.second});
if(nums.second.first != -1)mp[lower_bound(compress.begin(),compress.end(),nums.second.first) - compress.begin()].push_back({i,nums.second.second});
nums = get(nums);
}
}
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:89:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | for(int i = 0;i<compress.size();i++){
| ~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
111 ms |
246920 KB |
Output is correct |
| 2 |
Correct |
119 ms |
246836 KB |
Output is correct |
| 3 |
Correct |
130 ms |
250212 KB |
Output is correct |
| 4 |
Correct |
130 ms |
250304 KB |
Output is correct |
| 5 |
Correct |
151 ms |
258504 KB |
Output is correct |
| 6 |
Correct |
149 ms |
259896 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
117 ms |
247136 KB |
Output is correct |
| 2 |
Correct |
112 ms |
247116 KB |
Output is correct |
| 3 |
Correct |
2055 ms |
416020 KB |
Output is correct |
| 4 |
Correct |
2169 ms |
421616 KB |
Output is correct |
| 5 |
Correct |
2692 ms |
440448 KB |
Output is correct |
| 6 |
Correct |
2735 ms |
445932 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
812 ms |
344824 KB |
Output is correct |
| 2 |
Correct |
785 ms |
351152 KB |
Output is correct |
| 3 |
Correct |
1676 ms |
390176 KB |
Output is correct |
| 4 |
Correct |
1803 ms |
393800 KB |
Output is correct |
| 5 |
Correct |
2877 ms |
441860 KB |
Output is correct |
| 6 |
Correct |
3002 ms |
450092 KB |
Output is correct |
