#include <bits/stdc++.h>
#include "circus.h"
// #include "grader.cpp"
#define fi first
#define se second
#define mp make_pair
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
if (a < b) {a = b; return true;} return false;
}
const int Nmax = 1e5 + 5;
const int oo = 1e9;
vector <int> a;
vector <int> fval, gval;
int mx[Nmax << 2];
int mn[Nmax << 2];
int d[Nmax][2];
int dp[Nmax];
int n,m;
void solve() {
priority_queue <pair <int, pair <int, int>>> heap;
for (int i = 0; i <= n; i++)
for (int j = 0; j < 2; j++)
d[i][j] = oo;
d[n][0] = 0;
heap.push(mp(0, mp(n, 0)));
while (heap.size()) {
int cur = -heap.top().fi;
int i = heap.top().se.fi;
int dir = heap.top().se.se;
heap.pop();
if (d[i][dir] != cur)
continue;
int j = i + ((dir == 0) ? -1 : 1);
if (j >= 0 && j <= n && mini(d[j][dir], cur + abs(a[i] - a[j])))
heap.push(mp(-d[j][dir], mp(j, dir)));
j = lower_bound(a.begin(), a.end(), a[i] + cur) - a.begin();
if (j <= n && mini(d[j][1], a[j] - a[i]))
heap.push(mp(-d[j][1], mp(j, 1)));
j = upper_bound(a.begin(), a.end(), a[i] - cur) - a.begin() - 1;
if (j >= 0 && mini(d[j][0], a[i] - a[j]))
heap.push(mp(-d[j][0], mp(j, 0)));
}
for (int i = 0; i <= n; i++)
dp[i] = min(d[i][0], d[i][1]);
}
void update(int id, int l, int r, int pos, pair <int, int> val) {
if (l > pos || r < pos)
return;
if (l == r)
return (void) (mini(mn[id], val.fi), maxi(mx[id], val.se));
int mid = (l + r) >> 1;
update(id << 1, l, mid, pos, val);
update(id << 1 | 1, mid + 1, r, pos, val);
mx[id] = max(mx[id << 1], mx[id << 1 | 1]);
mn[id] = min(mn[id << 1], mn[id << 1 | 1]);
}
pair <int, int> get(int id, int l, int r, int u, int v) {
if (l > v || r < u)
return mp(oo, -oo);
if (l >= u && r <= v)
return mp(mn[id], mx[id]);
int mid = (l + r) >> 1;
pair <int, int> lnode = get(id << 1, l, mid, u, v);
pair <int, int> rnode = get(id << 1 | 1, mid + 1, r, u, v);
return mp(min(lnode.fi, rnode.fi), max(lnode.se, rnode.se));
}
void init(int N, int M, int P[]) {
n = N;
m = M;
for (int i = 0; i < n; i++)
a.push_back(P[i]);
a.push_back(M);
sort(a.begin(), a.end());
solve();
for (int i = 0; i <= n; i++) {
fval.push_back(a[i] - dp[i]);
gval.push_back(a[i] + dp[i]);
}
sort(fval.begin(), fval.end());
fval.resize(unique(fval.begin(), fval.end()) - fval.begin());
sort(gval.begin(), gval.end());
gval.resize(unique(gval.begin(), gval.end()) - gval.begin());
for (int i = 1; i <= ((n + 1) << 2); i++)
mn[i] = oo, mx[i] = -oo;
for (int i = 0; i <= n; i++) {
int pos, val;
val = a[i] - dp[i];
pos = lower_bound(fval.begin(), fval.end(), val) - fval.begin();
update(1, 0, n, pos, mp(a[i], -oo));
val = a[i] = dp[i];
pos = lower_bound(gval.begin(), gval.end(), val) - gval.begin();
update(1, 0, n, pos, mp(oo, a[i]));
}
}
int minLength(int x) {
int pos;
int res = oo;
pos = lower_bound(fval.begin(), fval.end(), x) - fval.begin();
res = get(1, 0, n, pos, n).fi - x;
pos = upper_bound(gval.begin(), gval.end(), x) - gval.begin() - 1;
if (pos > 0)
mini(res, x - get(1, 0, n, 0, pos).se);
return res;
}
Compilation message
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 |
Correct |
149 ms |
6588 KB |
Output is correct |
| 2 |
Correct |
141 ms |
6588 KB |
Output is correct |
| 3 |
Correct |
146 ms |
6620 KB |
Output is correct |
| 4 |
Correct |
149 ms |
6588 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
149 ms |
6588 KB |
Output is correct |
| 2 |
Correct |
141 ms |
6588 KB |
Output is correct |
| 3 |
Correct |
146 ms |
6620 KB |
Output is correct |
| 4 |
Correct |
149 ms |
6588 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
149 ms |
6588 KB |
Output is correct |
| 2 |
Correct |
141 ms |
6588 KB |
Output is correct |
| 3 |
Correct |
146 ms |
6620 KB |
Output is correct |
| 4 |
Correct |
149 ms |
6588 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
