#include <bits/stdc++.h>
using namespace std;
const int MX = 3e5 + 10;
#define ll long long
// Split segment based on A array (call them A segment), view them as if they are disjoint
// The only time where a segment affects another is only when finding which A segment a lady will go to
// We will then split segments together in each A segment
// Observe that there will be only O(logMAX) splits
// And for each split there will only be at most 2 values, X and X+1
struct pli{
ll fi, se;
bool operator < (const pli& b) const{
return fi < b.fi || (fi == b.fi && se > b.se);
}
};
set<pli> s;
ll M; int N, Q;
ll arr[MX], ans[MX];
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> M >> N >> Q;
for(int i = 0; i < N; i++) cin >> arr[i];
s.insert({arr[0] - 1, 1});
for(int i = 0; i < N - 1; i++) s.insert({arr[i + 1] - arr[i] - 1, arr[i] + 1});
s.insert({M - arr[N - 1], arr[N - 1] + 1});
int idx = 1;
while(idx < MX && !s.empty()){
set<pli>::iterator it = s.end(); it--;
ll fv = ((*it).fi - 1) / 2, sv = ((*it).fi) / 2;
ll stf = (*it).se, sts = (*it).se + fv + 1;
ans[idx++] = stf + fv;
s.erase(it);
if(fv > 0) s.insert({fv, stf});
if(sv > 0) s.insert({sv, sts});
}
for(int i = 0; i < Q; i++){
ll x; cin >> x;
cout << ans[x] << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
102 ms |
21436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
186 ms |
57516 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
