Submission #464123

#	Time	Username	Problem	Language	Result	Execution time	Memory
464123		fskarica	ČVENK (COI15_cvenk)	C++14	78 / 100	567 ms	23144 KiB

cvenk

#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long
#define ld long double
#define fi first
#define se second
#define pii pair<ll, ll>
 
const ll MAX = 4e5 + 10;
ll n;
ll x, y;
ll id;
ll sol;
ll head;
ll black[MAX];
ll parent[MAX];
vector <pii> v;
vector <ll> veze[MAX];
 
pii movek(ll x, ll y, ll k) {
    while (k) {
        if (x == 0) {
            y = max(0ll, y - k);
            break;
        }
        if (y == 0) {
            x = max(0ll, x - k);
            break;
        }
 
        if ((x&-x) < (y&-y)) {
            if (k < (x&-x)) {
                x -= k;
                k = 0;
            }
            else {
                k -= x&-x;
                x -= x&-x;
            }
        }
        else {
            if (k < (y&-y)) {
                y -= k;
                k = 0;
            }
            else {
                k -= y&-y;
                y -= y&-y;
            }
        }
    }
 
    return {x, y};
}
 
bool compare(pii a, pii b) {
	ll raz = (a.fi + a.se) - (b.fi + b.se);
    if (raz > 0) {
        a = movek(a.fi, a.se, raz);
    }
    if (raz < 0) {
        b = movek(b.fi, b.se, -raz);
    }
 
    if (a.fi > b.fi) {
		return true;
    }
    else if (b.fi > a.fi) {
		return false;
    }
    else {
        if (raz > 0) {
			return false;
        }
        else {
			return true;
        }
    }
}
 
pii lca(pii a, pii b) {
	ll raz = (a.fi + a.se) - (b.fi + b.se);
    if (raz > 0) {
        a = movek(a.fi, a.se, raz);
    }
    if (raz < 0) {
        b = movek(b.fi, b.se, -raz);
    }
 
    if (a == b) {
        return a;
    }
 
    for (ll i = 30; i >= 0; i--) {
        pii pa = movek(a.fi, a.se, (1 << i));
        pii pb = movek(b.fi, b.se, (1 << i));
 
        if (pa == pb) continue;
 
        a = pa;
        b = pb;
    }
 
    return movek(a.fi, a.se, 1);
}
 
ll rek(ll pos) {
	ll zbr = 0;
	for (auto e : veze[pos]) {
		if (e == pos) continue;
        zbr += rek(e);
	}
 
    if (pos < n) zbr++;
 
    black[pos] = zbr;
    return zbr;
}
 
void tree() {
    vector <pair<pii, ll>> st;
 
    for (ll i = 0; i < n; i++) {
        if (st.empty()) {
			parent[i] = i;
            st.push_back({v[i], i});
            continue;
        }
 
        pii p = lca(st.back().fi, v[i]);
 
        ll bla = -1;
        while (!st.empty() && st.back().fi.fi + st.back().fi.se > p.fi + p.se) {
			bla = st.back().se;
			st.pop_back();
        }
 
        if (!st.empty()  && st.back().fi.fi + st.back().fi.se < p.fi + p.se) {
			parent[id] = st.back().se;
            parent[bla] = id;
 
			st.push_back({p, id});
			v.push_back(p);
 
			id++;
        }
        else if (st.empty()) {
			parent[id] = id;
            parent[bla] = id;
 
			st.push_back({p, id});
			v.push_back(p);
 
			id++;
        }
 
        parent[i] = st.back().se;
		st.push_back({v[i], i});
    }
 
    for (ll i = 0; i < id; i++) {
		if (parent[i] == i) continue;
        veze[parent[i]].push_back(i);
    }
 
    head = st[0].se;
}
 
void walk(ll now, ll pos) {
	sol = min(sol, now);
 
	for (auto e : veze[pos]) {
		ll lvl = (v[e].fi + v[e].se) - (v[pos].fi + v[pos].se);
        walk(now - (black[e] * 2 - n) * lvl, e);
	}
}
 
int main() {
	cin >> n;
	id = n;
 
    for (ll i = 1; i <= n; i++) {
        cin >> x >> y;
 
		v.push_back({x, y});
    }
 
    sort(v.begin(), v.end(), compare);
 
	tree();
    rek(head);
 
    ll zbr = 0;
    for (ll i = 0; i < n; i++) {
        zbr += v[i].fi + v[i].se;
        zbr -= v[head].fi + v[head].se;
    }
    sol = 2e18;
    walk(zbr, head);
 
	cout << sol << "\n";
 
	return 0;
}

• Subtask 1: 17 / 17
• Subtask 2: 21 / 21
• Subtask 3: 0 / 22
• Subtask 4: 40 / 40