#include "circus.h"
#include <cstdio>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;
typedef pair<int, int> pii;
const int inf = 1e9 + 7;
int n, mx;
int cp[100001];
int dp[100001];
int vis[100001];
map<int, int> mp;
struct node {
int it, cs;
node(int i, int c) : it(i), cs(c) {}
bool operator<(const node &p) const {
return cs > p.cs;
}
};
struct segnode {
int l, r, mn;
segnode() : l(-1), r(-1) {}
} ns[2 * 32 * 100000];
int _alloc() {
static int tp = 0;
ns[tp].mn = mx;
return tp++;
}
void update(int &i, int s, int e, int x, int y, int v) {
if (e < x || y < s) return;
if (i == -1) i = _alloc();
if (x <= s && e <= y) {
ns[i].mn = min(ns[i].mn, v);
return;
}
int m = (s + e) / 2;
update(ns[i].l, s, m, x, y, v);
update(ns[i].r, m + 1, e, x, y, v);
}
int query(int &i, int s, int e, int x) {
if (i == -1) return mx;
int ret = ns[i].mn;
if (s == e) return ret;
int m = (s + e) / 2;
if (x <= m) ret = min(ret, query(ns[i].l, s, m, x));
else ret = min(ret, query(ns[i].r, m + 1, e, x));
return ret;
}
int rt1, rt2;
int ls[100001];
int rs[100001];
void init(int N, int M, int P[]) {
n = N;
mx = M;
rt1 = _alloc(); rt2 = _alloc();
for (int i = 0; i < n; ++i) cp[i] = P[i];
sort(cp, cp + n);
cp[n] = mx;
for (int i = 0; i <= n; ++i) mp[cp[i]] = i, ls[i] = -inf, rs[i] = inf;
priority_queue<node> pq;
pq.emplace(n, 0);
while (!pq.empty()) {
node x = pq.top(); pq.pop();
if (vis[x.it]) continue;
mp.erase(cp[x.it]);
vis[x.it] = 1;
dp[x.it] = x.cs;
map<int, int>::iterator it;
it = mp.lower_bound(cp[x.it]);
if (it != mp.end()) {
ls[it->second] = max(ls[it->second], ls[x.it]);
pq.emplace(it->second, cp[it->second] - ls[it->second]);
}
if (it != mp.begin()) {
--it;
rs[it->second] = min(rs[it->second], rs[x.it]);
pq.emplace(it->second, rs[it->second] - cp[it->second]);
}
it = mp.lower_bound(cp[x.it] + dp[x.it]);
if (it != mp.end()) {
ls[it->second] = max(ls[it->second], cp[x.it]);
pq.emplace(it->second, cp[it->second] - ls[it->second]);
}
it = mp.lower_bound(cp[x.it] - dp[x.it] + 1);
if (it != mp.begin()) {
--it;
rs[it->second] = min(rs[it->second], cp[x.it]);
pq.emplace(it->second, rs[it->second] - cp[it->second]);
}
}
for (int i = 0; i <= n; ++i) {
update(rt1, 0, mx, 0, cp[i] - dp[i], cp[i]);
update(rt2, 0, mx, cp[i] + dp[i], mx, -cp[i]);
}
}
int minLength(int D) {
return min(query(rt1, 0, mx, D) - D, D + query(rt2, 0, mx, D));
}
Compilation message
grader.cpp: In function 'int main()':
grader.cpp:14:12: warning: unused variable 'max_code' [-Wunused-variable]
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]
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]
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]
scanf("%d", &Q);
~~~~~^~~~~~~~~~
grader.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &d);
~~~~~^~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
270 ms |
81784 KB |
Output is correct |
2 |
Correct |
330 ms |
81904 KB |
Output is correct |
3 |
Correct |
293 ms |
81904 KB |
Output is correct |
4 |
Correct |
299 ms |
82044 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
61 ms |
82044 KB |
Output is correct |
2 |
Correct |
63 ms |
82044 KB |
Output is correct |
3 |
Incorrect |
65 ms |
82044 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
61 ms |
82044 KB |
Output is correct |
2 |
Correct |
63 ms |
82044 KB |
Output is correct |
3 |
Incorrect |
65 ms |
82044 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
61 ms |
82044 KB |
Output is correct |
2 |
Correct |
63 ms |
82044 KB |
Output is correct |
3 |
Incorrect |
65 ms |
82044 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
270 ms |
81784 KB |
Output is correct |
2 |
Correct |
330 ms |
81904 KB |
Output is correct |
3 |
Correct |
293 ms |
81904 KB |
Output is correct |
4 |
Correct |
299 ms |
82044 KB |
Output is correct |
5 |
Correct |
61 ms |
82044 KB |
Output is correct |
6 |
Correct |
63 ms |
82044 KB |
Output is correct |
7 |
Incorrect |
65 ms |
82044 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
270 ms |
81784 KB |
Output is correct |
2 |
Correct |
330 ms |
81904 KB |
Output is correct |
3 |
Correct |
293 ms |
81904 KB |
Output is correct |
4 |
Correct |
299 ms |
82044 KB |
Output is correct |
5 |
Correct |
61 ms |
82044 KB |
Output is correct |
6 |
Correct |
63 ms |
82044 KB |
Output is correct |
7 |
Incorrect |
65 ms |
82044 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |