#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
long long mid = 0;
map<long long,long long> dp;
long long lim = 1e18;
long long solve(long long x){
if(x<mid)return 0;
if(dp.find(x)!=dp.end())return dp[x];
return dp[x]=(x<=lim?1LL:0LL)+solve(x/2)+solve((x-1)/2);
}
long long ge(long long l,long long r,long long x){
if(r-l+1<=mid){
return (l+r)/2;
}
long long len = r-l+1;
if(solve((len-1)/2)>=x){
return ge(l,l+((len-1)/2)-1,x);
}else{
return ge(l+((len+1)/2),r,x-solve((len-1)/2));
}
}
signed main() {
ios_base::sync_with_stdio(0);cin.tie(0);
long long m,n,q;
cin>>m>>n>>q;
long long arr[n+2];
arr[0] = 0;
for(int i = 1;i<=n;i++){
cin>>arr[i];
}
arr[n+1] = m+1;
while(q--){
long long x;cin>>x;
if(x<=n){
cout<<arr[x]<<endl;
continue;
}
x-=n;
long long l=1,r=1e18 , ans = 0;
lim = 1e18;
while(l<=r){
mid = (l+r)/2;
dp.clear();
long long all = 0;
for(int i = 0;i<=n;i++){
all+=solve(arr[i+1]-arr[i]-1);
}
if(all>=x){
ans = mid;
l = mid+1;
}else r = mid-1;
}
assert(ans!=0);
dp.clear();
mid = ans+1;
for(int i = 0;i<=n;i++){
x-=solve(arr[i+1]-arr[i]-1);
}
assert(x>=1);
dp.clear();
mid = ans;
lim = ans;
for(int i = 0;i<=n;i++){
if(x>solve(arr[i+1]-arr[i]-1)){
x-=solve(arr[i+1]-arr[i]-1);
}else{
assert(x>=1);
cout<<ge(arr[i]+1,arr[i+1]-1,x)<<endl;
break;
}
}
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
212 KB |
Output is correct |
2 |
Correct |
14 ms |
212 KB |
Output is correct |
3 |
Execution timed out |
4082 ms |
556 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
4045 ms |
484 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
4067 ms |
7924 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |