| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1072035 | mickey080929 | Arranging Tickets (JOI17_arranging_tickets) | 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.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
struct FenwickTree{
vector<ll> tree;
void init(ll n) {
tree.assign(n+1, 0);
}
void upd(ll i, ll v, ll n) {
i ++;
while (i <= n) {
tree[i] += v;
i += i & -i;
}
}
ll qry(ll i) {
i ++;
ll ret = 0;
while (i) {
ret += tree[i];
i -= i & -i;
}
return ret;
}
};
struct DisjointSet{
vector<ll> par;
vector<ll> lft;
void init(ll n) {
par.resize(n);
iota(par.begin(), par.end(), 0);
lft.resize(n);
iota(lft.begin(), lft.end(), 0);
}
ll Find(ll x) {
if (x == par[x]) return x;
return par[x] = Find(par[x]);
}
void Union(ll l, ll r) {
l = Find(l);
r = Find(r);
lft[r] = lft[l];
par[l] = r;
}
};
FenwickTree seg;
DisjointSet dsu;
SegmentTree seg2;
struct Move{
ll A, B, C;
};
ll N, M;
ll solve(ll X, vector<ll> &use, vector<Move> &a) {
seg.init(N);
dsu.init(N);
ll j = 0;
ll ans = 0;
for (ll i=0; i<N-1; i++) {
ll t = i-1;
while (t >= 0) {
if (use[t] + seg.qry(t) <= use[i]) {
dsu.Union(t, i);
}
else break;
t = dsu.lft[i] - 1;
}
while (j < M && a[j].B-1 == i) {
ll p = dsu.Find(a[j].A);
ll mx = use[p] + seg.qry(p);
if (mx == X) {
j ++;
continue;
}
ll temp = min(a[j].C, (X - mx) / 2);
seg.upd(a[j].A, temp * 2, N);
seg.upd(a[j].B, -temp * 2, N);
ans += temp;
ll cur = mx + temp * 2;
t = dsu.lft[p] - 1;
while (t >= 0) {
if (use[t] + seg.qry(t) <= cur) {
dsu.Union(t, p);
}
else break;
t = dsu.lft[p] - 1;
}
j ++;
}
}
return ans;
}
int main() {
ios_base :: sync_with_stdio(false); cin.tie(NULL);
cin >> N >> M;
vector<Move> a(M);
ll tot = 0;
for (ll i=0; i<M; i++) {
cin >> a[i].A >> a[i].B >> a[i].C;
a[i].A --; a[i].B --;
if (a[i].A > a[i].B) swap(a[i].A, a[i].B);
tot += a[i].C;
}
sort(a.begin(), a.end(), [&] (Move &u, Move &v) {
if (u.B == v.B) return u.A > v.A;
return u.B < v.B;
});
vector<ll> use(N, 0);
seg.init(N);
for (ll i=0; i<M; i++) {
seg.upd(a[i].B, a[i].C, N);
seg.upd(0, a[i].C, N);
seg.upd(a[i].A, -a[i].C, N);
}
for (ll i=0; i<N; i++) {
use[i] = seg.qry(i);
}
ll ans = tot;
ll lo = tot, hi = tot + min(1000000000LL, tot);
while (lo <= hi) {
ll mid = (lo + hi) / 2;
ll ret1 = mid - solve(mid, use, a);
ll ret2 = mid+1 - solve(mid+1, use, a);
ans = min({ans, ret1, ret2});
if (ret1 > ret2) {
lo = mid + 2;
}
else {
hi = mid - 1;
}
}
cout << ans << '\n';
}