| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1217721 | InvMOD | Circus (Balkan15_CIRCUS) | C++17 | 0 ms | 0 KiB |
#include "circus.h"
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define pi pair<int,int>
#define sz(v) (int)(v).size()
#define all(v) (v).begin(), (v).end()
#define compact(v) (v).erase(unique(all(v)), (v).end())
template<class T> using upq = priority_queue<T, vector<T>, greater<T>>;
template<class T> int lwrbound(const vector<T>& a, const T& b, const int s = 0){return int(lower_bound(s + all(a), b) - a.begin());}
template<class T> int uprbound(const vector<T>& a, const T& b, const int s = 0){return int(upper_bound(s + all(a), b) - a.begin());}
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define ROF(i, a, b) for(int i = (a); i >= (b); i--)
#define sumof(x) accumulate(all(x), 0ll)
#define dbg(x) "[" << #x " = " << (x) << "]"
#define el "\n"
using ll = long long;
using ld = long double;
template<class T> bool ckmx(T& a, const T b){return (a < b ? a = b, true : false);}
template<class T> bool ckmn(T& a, const T b){return (a > b ? a = b, true : false);}
const int N = 2e5 + 5, INF = 2e9;
vector<int> posL, optL, posR, optR;
void init(int n, int m, vector<int> p){
p.eb(m); sort(all(p)); ++n;
vector<int> dist(2 * n, INF);
{ // dijkstra
int start = lwrbound(p, m); dist[start] = dist[start + n] = 0;
priority_queue<pi> pq; pq.emplace(0, start); pq.emplace(0, start + n);
while(sz(pq)){
pi e = pq.top(); pq.pop();
int x = e.se;
if(e.fi > dist[x]) continue;
// x can't go direct to next, so we have to increase the length
auto cost = [&](int u, int v) -> int{
u = (u < n ? u : u - n);
v = (v < n ? v : v - n);
return (p[u] - p[v] < 0 ? p[v] - p[u] : p[u] - p[v]);
};
if(x < n){
// go up
int nxt = x + 1;
if(nxt < n){
if(p[nxt] - p[x] < dist[x]){
if(ckmn(dist[nxt], dist[x] + cost(nxt, x))){
pq.emplace(-dist[nxt], nxt);
}
}
}
}
else{
// go down
int nxt = x - 1;
if(nxt >= 0){
if(p[nxt - n] - p[x - n] < dist[x]){
if(ckmn(dist[nxt], dist[x] + cost(nxt, x))){
pq.emplace(-dist[nxt], nxt);
}
}
}
}
// x can go directly to next now (require: abs(p[next] - p[x]) >= dist[x])
int nxtU = lwrbound(p, p[x % n] + dist[x]);
if(nxtU < n && cost(x, nxtU) >= dist[x]){
if(ckmn(dist[nxtU], cost(x, nxtU))){
pq.emplace(-dist[nxtU], nxtU);
}
}
int nxtD = uprbound(p, p[x % n] - dist[x]) - 1 + n;
if(nxtD >= n){
if(ckmn(dist[nxtD], cost(x, nxtD))){
pq.emplace(-dist[nxtD], nxtD);
}
}
}
}
// p[i] > d -> require: p[i] - d >= dist[i] -> p[i] - dist[i] >= d (1)
// the answer will be p[i] - d so we will take the minimum p[i] that has (1)
{
vector<pi> comp;
FOR(i, 0, n - 1){
int d = min(dist[i], dist[i + n]);
comp.eb(p[i] - d, p[i]);
}
sort(all(comp), greater<pi>());
for(pair<int,int> e : comp){
int req = e.fi, pos = e.se;
if(!sz(posR) || req != posR.back()){
posR.eb(req);
optR.eb(pos);
}
else ckmn(optR.back(), pos);
}
FOR(i, 1, sz(posR) - 1) ckmn(posR[i], posR[i - 1]);
reverse(all(posR)), reverse(all(optR));
}
// p[i] < d -> require: d - p[i] >= dist[i] -> d >= dist[i] + p[i] (2)
// the answer will be d - p[i] so we will take the maximum that has (2)
{
vector<pi> comp;
FOR(i, 0, n - 1){
int d = min(dist[i], dist[i + n]);
comp.eb(p[i] + d, p[i]);
}
sort(all(comp));
for(pair<int,int> e : comp){
int req = e.fi, pos = e.se;
if(!sz(posL) || posL.back() != req){
posL.eb(req);
optL.eb(pos);
}
else ckmx(optL.back(), pos);
}
FOR(i, 1, sz(posL) - 1) ckmx(optL[i], optL[i - 1]);
}
}
int minLength(int d){
int ans = 2e9;
int pL = uprbound(posL, d) - 1;
if(pL >= 0){
ckmn(ans, d - optL[pL]);
}
int pR = lwrbound(posR, d);
if(pR < sz(posR)){
ckmn(ans, optR[pR] - d);
}
return ans;
}