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 <iostream>
#include <vector>
#include <set>
using namespace std;
struct nes{
int l, r;
friend bool operator <(nes x, nes y){
if(x.r - x.l + 1 == y.r - y.l + 1)
return x.l < y.l;
return x.r - x.l + 1 > y.r - y.l + 1;
}
};
int m, n, q, a[300005], c[300005];
multiset <nes> s;
set <int> b;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> m >> n >> q;
for(int i = 1 ; i <= n ; ++i){
cin >> a[i];
c[i] = a[i];
}
if(a[1] != 1){
s.insert((nes){1, a[1] - 1});
}
for(int i = 2 ; i <= n ; ++i){
if(a[i] != a[i - 1] + 1){
s.insert((nes){a[i - 1] + 1, a[i] - 1});
}
}
if(a[n] != m){
s.insert((nes){a[n] + 1, m});
}
for(int i = n + 1 ; i <= min(m, 300000) ; ++i){
nes o = *s.begin();
s.erase(s.begin());
int mid = (o.l + o.r) / 2;
c[i] = mid;
if(mid > o.l){
s.insert((nes){o.l, mid - 1});
}
if(o.r > mid){
s.insert((nes){mid + 1, o.r});
}
}
for(int i = 0 ; i < q ; ++i){
int x;
cin >> x;
cout << c[x] << endl;
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |