oj.uz

Submission #464123

# Submission time Handle Problem Language Result Execution time Memory
464123 2021-08-12T12:09:49 Z fskarica ČVENK (COI15_cvenk) C++14
78 / 100
 567 ms 23144 KB 
#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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9704 KB Output is correct
2 Correct 7 ms 9712 KB Output is correct
3 Correct 7 ms 9652 KB Output is correct
4 Correct 7 ms 9664 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9676 KB Output is correct
2 Correct 7 ms 9612 KB Output is correct
3 Correct 6 ms 9700 KB Output is correct
4 Correct 8 ms 9708 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 127 ms 23144 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 567 ms 19440 KB Output is correct
2 Correct 567 ms 19440 KB Output is correct
3 Correct 131 ms 22404 KB Output is correct
4 Correct 134 ms 19320 KB Output is correct
5 Correct 122 ms 18688 KB Output is correct