This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/*
ID: 5ak0
PROG:
LANG: C++11
*/
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define mpr make_pair
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1e9 + 7, MAXN = 3e5 + 10;
set <pair<int, pii> > s;
int m, n, q;
int a[MAXN], ans[MAXN];
int main(){
cin >> m >> n >> q;
for (int i = 1; i <= n; ++i){
cin >> a[i];
ans[i] = a[i];
}
sort (a + 1, a + n + 1);
a[n + 1] = m + 1;
for (int i = 0; i <= n; ++i){
if (a[i] + 1 == a[i + 1])
continue;
s.insert({-((a[i + 1] - 1) - (a[i] + 1)), {a[i] + 1, a[i + 1] - 1}});
}
for (int i = n + 1; i <= MAXN; ++i){
pair <int, pii> kek = *s.begin();
int mid = (kek.sc.fr + kek.sc.sc) / 2;
if (kek.sc.fr <= mid - 1)
s.insert({-((mid - 1) - (kek.sc.fr)), {kek.sc.fr, mid - 1}});
if (mid + 1 <= kek.sc.sc)
s.insert({-((kek.sc.sc) - (mid + 1)), {mid + 1, kek.sc.sc}});
ans[i] = mid;
s.erase(kek);
// cout << i << ":\n";
// for (auto to : s)
// cout << to.sc.fr << " " << to.sc.sc << "\n";
//cerr << kek.fr << " " << kek.sc << " " << mid << "\n";
}
for (int i = 1; i <= q; ++i){
int x;
cin >> x;
cout << ans[x] << "\n";
}
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... |