Submission #1071963

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071963		mickey080929	Arranging Tickets (JOI17_arranging_tickets)	C++17	100 / 100	3642 ms	12576 KiB

arranging_tickets

#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
 
struct SegmentTree{
	vector<ll> tree;
	vector<ll> lazy;
	void init(ll n) {
		ll sz = 1 << __lg(n-1) + 2;
		tree.assign(sz, 0);
		lazy.assign(sz, 0);
	}
	void build(ll node, ll s, ll e, vector<ll> &v) {
		lazy[node] = 0;
		if (s == e) {
			tree[node] = v[s];
			return;
		}
		ll mid = s + e >> 1;
		build(node*2, s, mid, v);
		build(node*2+1, mid+1, e, v);
		tree[node] = max(tree[node*2], tree[node*2+1]);
	}
	void propagate(ll node, ll s, ll e) {
		tree[node] += lazy[node];
		if (s != e) {
			lazy[node*2] += lazy[node];
			lazy[node*2+1] += lazy[node];
		}
		lazy[node] = 0;
	}
	void update(ll node, ll s, ll e, ll l, ll r, ll v) {
		propagate(node, s, e);
		if (l > e || s > r) return;
		if (l <= s && e <= r) {
			lazy[node] = v;
			propagate(node, s, e);
			return;
		}
		ll mid = s + e >> 1;
		update(node*2, s, mid, l, r, v);
		update(node*2+1, mid+1, e, l, r, v);
		tree[node] = max(tree[node*2], tree[node*2+1]);
	}
	ll query(ll node, ll s, ll e, ll l, ll r) {
		propagate(node, s, e);
		if (l > e || s > r) return 0;
		if (l <= s && e <= r) return tree[node];
		ll mid = s + e >> 1;
		return max(query(node*2, s, mid, l, r), query(node*2+1, mid+1, e, l, r));
	}
};
 
SegmentTree seg;
 
struct Move{
	ll A, B, C;
};
 
ll N, M;
 
ll solve(ll X, vector<ll> &use, vector<Move> &a) {
	seg.build(1, 0, N-1, use);
	ll ans = 0;
	for (ll i=0; i<M; i++) {
		ll mx = seg.query(1, 0, N-1, a[i].A, a[i].B-1);
		if (mx == X) continue;
		seg.update(1, 0, N-1, a[i].A, a[i].B-1, min(a[i].C, (X - mx) / 2) * 2);
		ans += min(a[i].C, (X - mx) / 2);
	}
	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.update(1, 0, N-1, a[i].B, N-1, a[i].C);
		seg.update(1, 0, N-1, 0, a[i].A-1, a[i].C);
	}
	for (ll i=0; i<N; i++) {
		use[i] = seg.query(1, 0, N-1, i, i);
	}
	ll ans = tot - solve(tot, use, a);
	ll lo = tot+1, hi = tot + min(1000000000LL, ans);
	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