#ifndef ETHANKIM8683
#include "circus.h"
#endif
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <cstdio>
using namespace std;
using I = int;
const I N = 100000;
const I LOGN = 17;
const I MIN = -1e9;
const I MAX = 1e9;
vector<I> unqs;
map<I, I> unvs;
vector<I> cpss1;
vector<I> cpss2;
priority_queue<pair<I, I>, vector<pair<I, I>>, greater<pair<I, I>>> que;
I diss[N + 1];
I ps1[N + 1];
I ps2[N + 1];
void add(I dis, I a) {
if (dis < diss[a]) {
diss[a] = dis;
que.push({dis, a});
}
}
void unq1() {
sort(unqs.begin(), unqs.end());
unqs.erase(unique(unqs.begin(), unqs.end()), unqs.end());
}
void unq2() {
sort(cpss1.begin(), cpss1.end());
cpss1.erase(unique(cpss1.begin(), cpss1.end()), cpss1.end());
}
void unq3() {
sort(cpss2.begin(), cpss2.end());
cpss2.erase(unique(cpss2.begin(), cpss2.end()), cpss2.end());
}
I cps1(I x) {
return lower_bound(cpss1.begin(), cpss1.end(), x) - cpss1.begin();
}
I cps2(I x) {
return upper_bound(cpss2.begin(), cpss2.end(), x) - cpss2.begin() - 1;
}
void init(I n, I m, I p_arr[]) {
for (I i = 0; i < n; i++)
unqs.push_back(p_arr[i]);
unq1();
fill_n(diss, unqs.size(), MAX);
for (I i = 0; i < unqs.size(); i++)
unvs.insert({unqs[i], i});
add(m - unqs.back(), unqs.size() - 1);
while (!que.empty() && !unvs.empty()) {
const auto [dis, a] = que.top();
que.pop();
if (dis != diss[a])
continue;
const I p1 = unqs[a];
unvs.erase(p1);
if (!unvs.empty()) {
auto it = unvs.upper_bound(p1);
if (it != unvs.end()) {
const auto [p2, b] = *it;
I dis = p2 - p1;
if (dis >= diss[a])
add(dis, b);
}
if (it-- != unvs.begin()) {
const auto [p2, b] = *it;
I dis = p1 - p2;
if (dis >= diss[a])
add(dis, b);
}
auto upp_it = unvs.lower_bound(p1 + dis);
auto low_it = unvs.upper_bound(p1 - dis);
if (upp_it != unvs.end())
add(upp_it->first - p1, upp_it->second);
if (low_it-- != unvs.begin())
add(p1 - low_it->first, low_it->second);
}
}
for (I i = 0; i < unqs.size(); i++) {
cpss1.push_back(unqs[i] - diss[i]);
cpss2.push_back(unqs[i] + diss[i]);
}
unq2();
unq3();
fill_n(ps1, cpss1.size(), MAX);
fill_n(ps2, cpss2.size(), MIN);
for (I i = 0; i < unqs.size(); i++) {
const I low = cps1(unqs[i] - diss[i]);
const I upp = cps2(unqs[i] + diss[i]);
ps1[low] = min(ps1[low], unqs[i]);
ps2[upp] = max(ps2[upp], unqs[i]);
}
for (I i = cpss1.size() - 1; i - 1 >= 0; i--)
ps1[i - 1] = min(ps1[i - 1], ps1[i]);
for (I i = 0; i + 1 < cpss2.size(); i++)
ps2[i + 1] = max(ps2[i + 1], ps2[i]);
}
I minLength(I d) {
I res = MAX;
const I upp = cps1(d);
const I low = cps2(d);
if (upp < cpss1.size())
res = min(res, ps1[upp] - d);
if (low >= 0)
res = min(res, d - ps2[low]);
return res;
}
#ifdef ETHANKIM8683
#include <iostream>
#include <cstdio>
I main(void) {
cin.tie(0)->sync_with_stdio(0);
I n, m;
cin >> n >> m;
static I p[N];
for (I i = 0; i < n; i++)
cin >> p[i];
init(n, m, p);
while (true) {
I d = -1;
cin >> d;
if (d == -1)
break;
printf("%i\n", minLength(d));
}
return 0;
}
#endif
Compilation message
circus.cpp: In function 'void init(I, I, I*)':
circus.cpp:63:19: warning: comparison of integer expressions of different signedness: 'I' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for (I i = 0; i < unqs.size(); i++)
| ~~^~~~~~~~~~~~~
circus.cpp:95:19: warning: comparison of integer expressions of different signedness: 'I' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | for (I i = 0; i < unqs.size(); i++) {
| ~~^~~~~~~~~~~~~
circus.cpp:103:19: warning: comparison of integer expressions of different signedness: 'I' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
103 | for (I i = 0; i < unqs.size(); i++) {
| ~~^~~~~~~~~~~~~
circus.cpp:111:23: warning: comparison of integer expressions of different signedness: 'I' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | for (I i = 0; i + 1 < cpss2.size(); i++)
| ~~~~~~^~~~~~~~~~~~~~
circus.cpp: In function 'I minLength(I)':
circus.cpp:119:11: warning: comparison of integer expressions of different signedness: 'const I' {aka 'const int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
119 | if (upp < cpss1.size())
| ~~~~^~~~~~~~~~~~~~
grader.cpp: In function 'int main()':
grader.cpp:14:12: warning: unused variable 'max_code' [-Wunused-variable]
14 | long long max_code;
| ^~~~~~~~
grader.cpp:16:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
16 | scanf("%d%d", &N, &M);
| ~~~~~^~~~~~~~~~~~~~~~
grader.cpp:18:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
18 | scanf("%d", &P[i]);
| ~~~~~^~~~~~~~~~~~~
grader.cpp:21:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
21 | scanf("%d", &Q);
| ~~~~~^~~~~~~~~~
grader.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
23 | scanf("%d", &d);
| ~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
127 ms |
7648 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
127 ms |
7648 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
127 ms |
7648 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
