| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1315983 | tkhoi13 | Palembang Bridges (APIO15_bridge) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define db double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define pb push_back
#define all(x) begin(x), end(x)
#define allr(x) rbegin(x), rend(x)
#define szx(x) ((int)(x).size())
#define FOR(i, a, b) for (int i = a, _b = (b); i <= _b; ++i)
#define ROF(i, a, b) for (int i = a, _b = (b); i >= _b; --i)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i)
#define endl '\n'
#define inf 1000000007
#define mod 1000000007
// #define mod 998244353
using namespace std;
using namespace __gnu_pbds;
void setIO() {
ios::sync_with_stdio(0);
cin.tie(0);
}
void openFile(string filename = "") {
if (!filename.empty())
if (ifstream(filename + ".in")) {
freopen((filename + ".in").c_str(), "r", stdin);
freopen((filename + ".out").c_str(), "w", stdout);
}
}
const int MAX = 1e5 + 5;
int n, k;
vector<pll> a;
vector<int> compress{-1};
ll s1 = 0;
struct SegmentTree {
vector<pair<int, ll>> st;
int _n;
SegmentTree(int _n) {
n = _n;
st.resize(4 * n);
}
void update(pii x, int s = 1) {
update(x.fi, s, s * compress[x.fi]);
update(x.se, s, s * compress[x.se]);
}
void update(int x, int y, ll z, int id = 1, int l = 1, int r = n) {
if (l == r) {
st[id].fi += y;
st[id].se += z;
return;
}
int mid = (l + r) >> 1;
if (x <= mid)
update(x, y, z, 2 * id, l, mid);
else
update(x, y, z, 2 * id + 1, mid + 1, r);
st[id].fi = st[2 * id].fi + st[2 * id + 1].fi;
st[id].se = st[2 * id].se + st[2 * id + 1].se;
}
int med(int id = 1, int l = 1, int r = n, int acc = 0) {
if (l == r) return l;
int mid = (l + r) >> 1;
if (acc + st[2 * id].fi > getmid())
return med(2 * id, l, mid, acc);
else
return med(2 * id + 1, mid + 1, r, acc + st[2 * id].fi);
}
pair<int, ll> query(int u, int v = n, int id = 1, int l = 1, int r = n) {
if (u > v) return {0, 0};
if (r < u || l > v) return {0, 0};
if (l >= u && r <= v) return st[id];
int mid = (l + r) >> 1;
pair<int, ll> q1 = query(u, v, 2 * id, l, mid);
pair<int, ll> q2 = query(u, v, 2 * id + 1, mid + 1, r);
return {q1.fi + q2.fi, q1.se + q2.se};
}
int getmid() { return (st[1].fi + 1) / 2; }
ll getans() {
int m = med();
pair<int, ll> q1 = query(1, m - 1), q2 = query(m + 1);
return q2.se - q1.se - 1LL * (q2.fi - q1.fi) * compress[m];
}
};
void solve() {
int m = szx(a);
s1 += m;
REP(i, m) compress.pb(a[i].fi), compress.pb(a[i].se);
sort(all(compress));
sort(all(a), [&](pll x, pll y) { return x.fi + x.se < y.fi + y.se; });
compress.erase(unique(all(compress)), compress.end());
SegmentTree pref(szx(compress)), suff(szx(compress));
REP(i, m) {
a[i].fi = lower_bound(all(compress), a[i].fi) - compress.begin();
a[i].se = lower_bound(all(compress), a[i].se) - compress.begin();
suff.update(a[i]);
}
ll ans = m != 0 ? 1e18 : 0;
if (k == 1)
ans = suff.getans();
else
REP(i, m) {
ans = min(ans, pref.getans() + suff.getans());
suff.update(a[i], -1);
pref.update(a[i]);
}
cout << s1 + ans;
}
void input() {
cin >> k >> n;
REP(i, n) {
char A, B;
int s, t;
cin >> A >> s >> B >> t;
if (A != B)
a.pb({s, t});
else
s1 += abs(s - t);
}
}
void preprocess() {}
void reset() {}
int main() {
setIO();
openFile("main");
int t = 1;
// cin >> t;
preprocess();
while (t--) {
reset();
input();
solve();
}
}#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define db double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define pb push_back
#define all(x) begin(x), end(x)
#define allr(x) rbegin(x), rend(x)
#define szx(x) ((int)(x).size())
#define FOR(i, a, b) for (int i = a, _b = (b); i <= _b; ++i)
#define ROF(i, a, b) for (int i = a, _b = (b); i >= _b; --i)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i)
#define endl '\n'
#define inf 1000000007
#define mod 1000000007
// #define mod 998244353
using namespace std;
using namespace __gnu_pbds;
void setIO() {
ios::sync_with_stdio(0);
cin.tie(0);
}
void openFile(string filename = "") {
if (!filename.empty())
if (ifstream(filename + ".in")) {
freopen((filename + ".in").c_str(), "r", stdin);
freopen((filename + ".out").c_str(), "w", stdout);
}
}
const int MAX = 1e5 + 5;
int n, k;
vector<pll> a;
vector<int> compress{-1};
ll s1 = 0;
struct SegmentTree {
vector<pair<int, ll>> st;
int _n;
SegmentTree(int _n) {
n = _n;
st.resize(4 * n);
}
void update(pii x, int s = 1) {
update(x.fi, s, s * compress[x.fi]);
update(x.se, s, s * compress[x.se]);
}
void update(int x, int y, ll z, int id = 1, int l = 1, int r = n) {
if (l == r) {
st[id].fi += y;
st[id].se += z;
return;
}
int mid = (l + r) >> 1;
if (x <= mid)
update(x, y, z, 2 * id, l, mid);
else
update(x, y, z, 2 * id + 1, mid + 1, r);
st[id].fi = st[2 * id].fi + st[2 * id + 1].fi;
st[id].se = st[2 * id].se + st[2 * id + 1].se;
}
int med(int id = 1, int l = 1, int r = n, int acc = 0) {
if (l == r) return l;
int mid = (l + r) >> 1;
if (acc + st[2 * id].fi > getmid())
return med(2 * id, l, mid, acc);
else
return med(2 * id + 1, mid + 1, r, acc + st[2 * id].fi);
}
pair<int, ll> query(int u, int v = n, int id = 1, int l = 1, int r = n) {
if (u > v) return {0, 0};
if (r < u || l > v) return {0, 0};
if (l >= u && r <= v) return st[id];
int mid = (l + r) >> 1;
pair<int, ll> q1 = query(u, v, 2 * id, l, mid);
pair<int, ll> q2 = query(u, v, 2 * id + 1, mid + 1, r);
return {q1.fi + q2.fi, q1.se + q2.se};
}
int getmid() { return (st[1].fi + 1) / 2; }
ll getans() {
int m = med();
pair<int, ll> q1 = query(1, m - 1), q2 = query(m + 1);
return q2.se - q1.se - 1LL * (q2.fi - q1.fi) * compress[m];
}
};
void solve() {
int m = szx(a);
s1 += m;
REP(i, m) compress.pb(a[i].fi), compress.pb(a[i].se);
sort(all(compress));
sort(all(a), [&](pll x, pll y) { return x.fi + x.se < y.fi + y.se; });
compress.erase(unique(all(compress)), compress.end());
SegmentTree pref(szx(compress)), suff(szx(compress));
REP(i, m) {
a[i].fi = lower_bound(all(compress), a[i].fi) - compress.begin();
a[i].se = lower_bound(all(compress), a[i].se) - compress.begin();
suff.update(a[i]);
}
ll ans = m != 0 ? 1e18 : 0;
if (k == 1)
ans = suff.getans();
else
REP(i, m) {
ans = min(ans, pref.getans() + suff.getans());
suff.update(a[i], -1);
pref.update(a[i]);
}
cout << s1 + ans;
}
void input() {
cin >> k >> n;
REP(i, n) {
char A, B;
int s, t;
cin >> A >> s >> B >> t;
if (A != B)
a.pb({s, t});
else
s1 += abs(s - t);
}
}
void preprocess() {}
void reset() {}
int main() {
setIO();
openFile("main");
int t = 1;
// cin >> t;
preprocess();
while (t--) {
reset();
input();
solve();
}
}