# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1254348 | pramad712 | Circus (Balkan15_CIRCUS) | C++20 | 162 ms | 1548 KiB |
#include "circus.h"
#include <bits/stdc++.h>
using namespace std;
deque<int> positions;
deque<int> minimals;
int binary_search(int placement) {
int minimal = 0, maximal = 1000000000;
while (minimal < maximal) {
int middle = (minimal + maximal) / 2;
int end = placement + middle;
int index = upper_bound(positions.begin(), positions.end(), end) - positions.begin() - 1;
if (index <= -1) {
minimal = middle + 1;
continue;
}
int height = positions[index] - placement;
if (height >= minimals[index]) {
maximal = middle;
}
else {
minimal = middle + 1;
}
}
return minimal;
}
void init(int N, int M, int P[]){
sort(P, P + N, greater<>());
positions.push_back(M);
minimals.push_back(0);
for (int index = 0; index < N; index++) {
int position = P[index];
minimals.push_front(binary_search(position));
positions.push_front(position);
}
minimals.push_front(binary_search(0));
positions.push_front(0);
}
int minLength(int placement) {
return binary_search(placement);
}
// int main() {
// int N, M, Q;
// cin >> N >> M >> Q;
//
// int P[N];
//
// for (int index = 0; index < N; index++) {
// cin >> P[index];
// }
//
// init(N, M, P);
//
// for (int q = 0; q < Q; q++) {
// int D;
// cin >> D;
//
// cout << minLength(D) << "\n";
// }
//
// return 0;
// }
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |