| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 264870 | Berted | Palembang Bridges (APIO15_bridge) | C++14 | 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.
#include <iostream>
#include <vector>
#include <algorithm>
#include <assert.h>
#define vi vector<int>
#define pub push_back
#define pii pair<int, int>
#define fst first
#define snd second
#define ll long long
using namespace std;
const int INF = 1e9;
const ll INF2 = 1e18;
int C2[200001], C2sz = 0;
struct BIT
{
ll fwk[2][200001], sum[2];
inline void upd(int t, int x, int v)
{
for (; x < C2sz; x += x & (-x)) {fwk[t][x] += v;}
sum[t] += v;
}
inline ll qry(int t, int x)
{
ll ret = 0;
for (; x; x -= x & (-x)) {ret += fwk[t][x];}
return ret;
}
};
int k, n, lfm, rgm; ll opt;
int C[200001], Csz = 0;
pii seg[2][100001]; int segSz[2];
ll res = 0;
BIT L[2], R[2];
inline void prep()
{
sort(C2, C2 + C2sz);
C2sz = unique(C2, C2 + C2sz) - C2;
}
inline int getCoord(int x)
{
return prev(upper_bound(C2, C2 + C2sz, x)) - C2;
}
inline ll eval(int k, int gx, int x)
{
if (x < 0 || x > INF) return INF2;
if (gx == -1) {gx = getCoord(x);}
return L[k].qry(0, gx) * x - L[k].qry(1, gx) + (R[k].sum[1] - R[k].qry(1, gx)) - x * (R[k].sum[0] - R[k].qry(0, gx));
}
inline ll solve(int t, int lf, int rg)
{
int M;
while (rg - lf > 3)
{
int M = lf + ((rg - lf) >> 1);
int gx = getCoord(M + 1);
if (eval(t, gx, M) < eval(t, gx2, M + 1)) {rg = M + 1;}
else {lf = M;}
}
int ans = lf;
for (int i = lf + 1; i <= rg; i++)
{
if (eval(t, -1, i) < eval(t, -1, ans)) {ans = i;}
}
return eval(t, -1, ans);
}
inline ll solve2(int t, int lf, int rg)
{
while (rg - lf > 3)
{
int M = lf + ((rg - lf) >> 1);
int gx = getCoord(M), gx2 = gx + (gx + 1 < C2sz && C2[gx + 1] == M + 1);
if (eval(t, gx, M) < eval(t, gx2, M + 1)) {rg = M + 1;}
else {lf = M;}
}
int ans = lf;
for (int i = lf + 1; i <= rg; i++)
{
if (eval(t, -1, i) < eval(t, -1, ans)) {ans = i;}
}
return ans;
}
inline ll eval2(int x, int l, int r)
{
if (l < 0 || r > INF || l > r) return INF2;
if (r < lfm) {return eval(0, -1, x) + eval(1, -1, r);}
else if (l > rgm) {return eval(0, -1, x) + eval(1, -1, l);}
else {return eval(0, -1, x) + opt;}
}
int main()
{
ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
//freopen("bridges.in", "r", stdin);
cin >> k >> n;
C2[C2sz++] = -1;
for (int i = 0; i < n; i++)
{
char c1, c2; int p1, p2; cin >> c1 >> p1 >> c2 >> p2;
if (p1 > p2) swap(p1, p2);
res += p2 - p1;
if (c1 != c2)
{
res++;
seg[0][segSz[0]++] = {p1, p2};
seg[1][segSz[1]++] = {p1 + p2, segSz[0] - 1};
C[Csz++] = p1 + p2;
C2[C2sz++] = p1;
C2[C2sz++] = p2;
}
}
prep();
//cout << res << "\n";
if (k == 1)
{
for (int i = 0; i < segSz[0]; i++)
{
int gx = getCoord(seg[0][i].snd);
L[0].upd(0, gx, 1);
L[0].upd(1, gx, seg[0][i].snd);
gx = getCoord(seg[0][i].fst);
R[0].upd(0, gx, 1);
R[0].upd(1, gx, seg[0][i].fst);
}
cout << res + 2 * solve(0, 0, INF) << "\n";
}
else
{
sort(seg[1], seg[1] + segSz[1]);
C[Csz++] = 0; C[Csz++] = 2 * INF; C[Csz++] = 2 * INF + 1;
sort(C, C + Csz);
Csz = unique(C, C + Csz) - C;
int j = 0;
for (int i = 0; i < segSz[0]; i++)
{
int gx = getCoord(seg[0][i].snd);
L[1].upd(0, gx, 1);
L[1].upd(1, gx, seg[0][i].snd);
gx = getCoord(seg[0][i].fst);
R[1].upd(0, gx, 1);
R[1].upd(1, gx, seg[0][i].fst);
}
ll ans = INF2;
for (int i = 0; i < Csz - 1; i++)
{
for (; j < segSz[1] && seg[1][j].fst <= C[i]; j++)
{
int idx = seg[1][j].snd, gx = getCoord(seg[0][idx].snd);
L[1].upd(0, gx, -1);
L[1].upd(1, gx, -seg[0][idx].snd);
L[0].upd(0, gx, 1);
L[0].upd(1, gx, seg[0][idx].snd);
gx = getCoord(seg[0][idx].fst);
R[1].upd(0, gx, -1);
R[1].upd(1, gx, -seg[0][idx].fst);
R[0].upd(0, gx, 1);
R[0].upd(1, gx, seg[0][idx].fst);
}
int idx = solve2(1, 0, INF); opt = eval(1, -1, idx);
int l = 0, r = idx;
while (l < r)
{
int M = l + ((r - l) >> 1);
if (eval(1, -1, M) > opt) {l = M + 1;}
else {r = M;}
}
lfm = l;
l = idx, r = INF + 1;
while (l < r)
{
int M = l + ((r - l) >> 1);
if (eval(1, -1, M) > opt) {r = M;}
else {l = M + 1;}
}
rgm = r - 1;
l = max(0, C[i] - INF), r = C[i] >> 1;
while (r - l > 3)
{
int M = l + ((r - l) >> 1);
if (eval2(M, C[i] - M, min(INF, C[i + 1] - 1 - M)) < eval2(M + 1, C[i] - M - 1, min(INF, C[i + 1] - 2 - M))) {r = M + 1;}
else {l = M;}
}
assert(l <= r);
int anss = l;
for (int j = l + 1; j <= r; j++)
{
if (eval2(j, C[i] - j, min(INF, C[i + 1] - 1 - j)) < eval2(anss, C[i] - anss, min(INF, C[i + 1] - 1 - anss))) {anss = j;}
}
ans = min(ans, eval2(anss, C[i] - anss, min(INF, C[i + 1] - 1 - anss)));
}
cout << 2 * ans + res << "\n";
}
return 0;
}