This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define pii pair<ll, ll>
#define fi first
#define se second
#define ll long long
const ll MX = 1e5 + 10;
struct range{
ll len, cnt, idx;
range(ll len, ll cnt, ll idx): len(len), cnt(cnt), idx(idx){}
// sort by largest len
bool operator < (const range& other) const{
return len > other.len || (len == other.len && idx < other.idx);
}
};
ll N, M, Q; vector<range> vec;
ll A[MX], B[MX];
void build(ll len, ll idx, vector<range>& R){
// big len, big cnt, small len, small cnt
ll bl = len + 1, bc = 0, sl = len, sc = 1;
if(bc != 0) R.push_back({bl, bc, idx});
if(sc != 0) R.push_back({sl, sc, idx});
ll one = 0;
while(bl > 0){
if(bl % 2 == 0){
// 4 3 -> (1 2) (1 1)
// 6 5 -> (2 3) (2 2)
bl = bl / 2, sl = sl / 2;
sc = bc + 2 * sc, bc = bc;
}else if(bl % 2 == 1){
// 3 2 -> (1 1) (0 1)
// 5 4 -> (2 2) (1 2)
bl = bl / 2, sl = (sl - 1) / 2;
sc = sc, bc = 2 * bc + sc;
}
if(bl == 1) one += bc;
else if(bl != 0 && bc != 0) R.push_back({bl, bc, idx});
if(sl == 1) one += sc;
else if(sl != 0 && sc != 0) R.push_back({sl, sc, idx});
}
R.push_back({1, one, idx});
}
ll bf(ll lf, ll rg, ll len, ll cnt){
ll mid = (lf + rg) / 2;
if((rg - lf + 1) == len) return mid;
vector<range> C;
ll curr = 0;
build(mid - lf, -1, C);
for(auto x : C)
if(x.len == len) curr += x.cnt;
if(cnt <= curr) return bf(lf, mid - 1, len, cnt);
else return bf(mid + 1, rg, len, cnt - curr);
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> M >> N >> Q;
for(ll i = 1; i <= N; i++){
cin >> A[i];
build(A[i] - A[i - 1] - 1, i, vec);
}
A[N + 1] = M + 1;
build(A[N + 1] - A[N] - 1, N + 1, vec);
for(ll i = 1; i <= Q; i++) cin >> B[i];
ll j = 1;
for(; j <= Q && B[j] <= N; j++) cout << A[B[j]] << '\n';
sort(vec.begin(), vec.end());
ll num = N + 1; // range_no
for(range x : vec){
ll len = x.len, cnt = x.cnt, idx = x.idx;
// cout << "At range " << A[idx - 1] + 1 << " " << A[idx] - 1 << " exists " << cnt << " length of " << len << '\n';
for(; j <= Q && B[j] < num + cnt; j++){
// cout << "Binser at " << A[idx - 1] + 1 << " " << A[idx] - 1 << " length of " << len << " number " << B[j] - num + 1 << '\n';
cout << bf(A[idx - 1] + 1, A[idx] - 1, len, B[j] - num + 1) << '\n';
}
num += cnt;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |