# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
73286 | 2018-08-28T06:40:10 Z | 강태규(#2268) | Circus (Balkan15_CIRCUS) | C++11 | 208 ms | 5752 KB |
#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, pr; node(int i, int c, int p) : it(i), cs(c), pr(p) {} bool operator<(const node &p) const { return cs > p.cs; } }; void update(priority_queue<node> &pq, int x) { if (x == -1) return; pii r(inf, -1); map<int, int>::iterator it; it = mp.lower_bound(cp[x] + dp[x]); if (it != mp.end()) r = min(r, pii(it->first - cp[x], it->second)); it = mp.lower_bound(cp[x] - dp[x] + 1); if (it != mp.begin()) --it, r = min(r, pii(cp[x] - it->first, it->second)); if (r.second != -1) pq.emplace(r.second, r.first, x); } int rt; void init(int N, int M, int P[]) { n = N; mx = M; 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; priority_queue<node> pq; pq.emplace(n, 0, -1); 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; update(pq, x.it); update(pq, x.pr); } for (int i = 0; i <= n; ++i) printf("%d %d\n", i, dp[i]); } int minLength(int D) { int ans = inf; for (int i = 0; i <= n; ++i) { if (dp[i] <= abs(D - cp[i])) ans = min(ans, abs(D - cp[i])); } return ans; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 208 ms | 5752 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 3 ms | 5752 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 3 ms | 5752 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 3 ms | 5752 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 208 ms | 5752 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 208 ms | 5752 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |