Submission #525296

#	Time	Username	Problem	Language	Result	Execution time	Memory
525296		Aldas25	Road Construction (JOI21_road_construction)	C++14	0 / 100	10082 ms	1521972 KiB

road_construction

#include <bits/stdc++.h>

using namespace std;

#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(0)
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define pb push_back
#define f first
#define s second
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAXN = 250100, MAXK = 20;
const ll MOD = 1e9+7;

const ll MAXD = 1e15;

struct fen1 {
    unordered_map<ll, ll> fen;

    void upd (ll p, ll x) {
        if (p <= 0) return;

        for (ll i = p; i < MAXD; i += i&(-i))
            fen[i] += x;
    }

    ll get (ll p) {
        if (p <= 0) return 0;

        ll ret = 0;
        for (ll i = p; i > 0; i -= i&(-i))
            ret += fen[i];
        return ret;
    }

    ll sum (ll a, ll b) {
        return get(b) - get(a-1);
    }

    void clear () {
        fen.clear();
    }
};

struct fen2 {
    unordered_map<ll, fen1> fen;

    void upd (ll x, ll y, ll d) {
        if (x <= 0) return;

        for (ll i = x; i < MAXD; i += i&(-i))
            fen[i].upd(y, d);
    }

    ll get (ll x, ll y) {
        if (x <= 0) return 0;

        ll ret = 0;
        for (ll i = x; i > 0; i -= i&(-i))
            ret += fen[i].get(y);
        return ret;
    }

    ll get (ll x, ll y11, ll y2) {
        if (x <= 0) return 0;

        ll ret = 0;
        for (ll i = x; i > 0; i -= i&(-i))
            ret += fen[i].sum(y11, y2);
        return ret;
    }

    ll sum (ll x1, ll y11, ll x2, ll y2) {
        return get(x2, y11, y2) - get(x1-1, y11, y2);
    }

    void clear () {
        for (auto p : fen) p.s.clear();
        fen.clear();
    }
};


int n, k;
ll x[MAXN], y[MAXN];

ll dst (int i, int j) {
    return abs(x[i] - x[j]) + abs(y[i] - y[j]);
}

fen2 tree1, tree2;
vector<pair<ll, ll>> points;

ll calcPairs (ll c) {
    tree1.clear();
    tree2.clear();

    ll ret = 0;
    ll BIG = 1e12;

    for (auto p : points) {
        ll cur1, cur2;

        cur1 = tree1.sum(0, p.f+p.s, p.s, BIG);
        cur2 = tree2.sum(p.s+1, p.f-p.s, BIG, BIG);

        ret += cur1+cur2;

        tree1.upd(p.s, c+p.f+p.s, +1);
        tree2.upd(p.s, c+p.f-p.s, +1);
    }

    return ret;
}

int main()
{
    FAST_IO;

    cin >> n >> k;
    FOR(i, 1, n) cin >> x[i] >> y[i];

    ll C = 1e10;
    FOR(i, 1, n) x[i] += 2*C, y[i] += C;

    FOR(i, 1, n) points.pb({x[i], y[i]});
    sort(points.begin(), points.end());

    ll le = 0, ri = 1e12;
    while (le < ri) {
        ll m = (le+ri)/2;
        ll p = calcPairs(m);

        if (p == 0) le = m+1;
        else ri = m;

    }

    cout << le << "\n";

    return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 6
• Subtask 3: 0 / 7
• Subtask 4: 0 / 20
• Subtask 5: 0 / 27
• Subtask 6: 0 / 35