Submission #1072036

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072036		mickey080929	Arranging Tickets (JOI17_arranging_tickets)	C++17	100 / 100	926 ms	9068 KiB

arranging_tickets

#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;

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';
}

• Subtask 1: 10 / 10
• Subtask 2: 35 / 35
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 15 / 15