| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 494478 | 8e7 | Circus (Balkan15_CIRCUS) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//Challenge: Accepted
#include "circus.h"
#pragma GCC optimize("Ofast")
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <bitset>
#include <set>
#include <queue>
#include <stack>
#include <assert.h>
#include <cmath>
#include <iomanip>
#include <random>
#include <unordered_map>
#include <chrono>
using namespace std;
void debug(){cout << endl;};
template<class T, class ...U> void debug(T a, U ... b){cout << a << " ", debug(b ...);};
template<class T> void pary(T l, T r) {
while (l != r) cout << *l << " ", l++;
cout << endl;
};
#define ll long long
#define ld long double
#define maxn 100005
#define mod 998244353
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const int inf = 1<<30;
struct BIT{
int bit[maxn];
void init() {
for (int i = 0;i < maxn;i++) bit[i] = inf;
}
void modify(int ind, int val) {
for (;ind < maxn;ind += ind & (-ind)) bit[ind] = min(bit[ind], val);
}
int query(int ind) {
int ret = inf;
for (;ind > 0;ind -= ind & (-ind)) ret = min(ret, bit[ind]);
return ret;
}
} pref, suf;
int M;
int d[maxn];
priority_queue<pii, vector<pii>, greater<pii> > pq;
vector<pii> front, back;
vector<int> fval, bval;
void init(int n, int m, int p[]){
sort(p, p + n);
for (int i = 0;i < n;i++) d[i] = inf;
pref.init(), suf.init();
suf.modify(maxn - n - 1, m), pref.modify(n, -m);
pq.push({m - p[n-1], n-1});
d[n-1] = m - p[n-1];
while (pq.size()) {
pii cur = pq.top();pq.pop();
if (cur.ff != d[cur.ss]) continue;
//debug("found", cur.ss, cur.ff);
auto add = [&] (int x, int val) {
if (val < d[x]) {
d[x] = val;
pq.push({d[x], x});
}
};
for (int i = 0;i < n;i++) {
if (abs(p[i] - p[cur.ss]) >= d[cur.ss]) {
add(i, abs(p[i] - p[cur.ss]);
}
}
/*
int ind = upper_bound(p, p + n, p[cur.ss] - d[cur.ss]) - p - 1;
if (ind >= 0) {
suf.modify(maxn - 1 - ind, p[cur.ss]);
add(ind, suf.query(maxn - 1 - ind) - p[ind]);
}
ind = lower_bound(p, p + n, p[cur.ss] + d[cur.ss]) - p;
if (ind < n) {
pref.modify(ind, -p[cur.ss]);
add(ind, pref.query(ind) + p[ind]);
}
if (cur.ss > 0) add(cur.ss-1, suf.query(maxn - cur.ss) - p[cur.ss-1]);
if (cur.ss < n - 1) add(cur.ss+1, pref.query(cur.ss+1) + p[cur.ss+1]);
*/
}
for (int i = 0;i < n;i++) {
back.push_back({p[i] - d[i], p[i]});
front.push_back({p[i] + d[i], p[i]});
}
sort(back.begin(), back.end()), sort(front.begin(), front.end());
fval.resize(n), bval.resize(n);
int cur = inf;
for (int i = n - 1;i >= 0;i--) {
cur = min(cur, back[i].ss);
bval[i] = cur;
}
M = m;
cur = 0;
for (int i = 0;i < n;i++) {
cur = max(cur, front[i].ss);
fval[i] = cur;
}
}
int minLength(int x) {
int ind = lower_bound(back.begin(), back.end(), make_pair(x, 0)) - back.begin();
int ans = M - x;
if (ind < front.size()) ans = min(ans, bval[ind] - x);
ind = upper_bound(front.begin(), front.end(), make_pair(x, 0)) - front.begin() - 1;
if (ind >= 0) ans = min(ans, x - fval[ind]);
return ans;
}
/*
6 15
1 3 4 7 8 11
4 20
3 8 13 18
1
10
*/