Submission #390117

#	Time	Username	Problem	Language	Result	Execution time	Memory
390117		apostoldaniel854	Road Construction (JOI21_road_construction)	C++14	0 / 100	10088 ms	257076 KiB

road_construction

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define dbg(x) cerr << #x << " " << x << "\n"

const int INF = 2e9;
const int MAX_N = 1e6;
vector <pair <ll, int>> v[1 + MAX_N];

int bin_search (vector <pair <ll, int>> &v, ll x) {
    int n = v.size ();
    int lb = 0, rb = n - 1, best = -1;
    while (lb <= rb) {
        int mid = (lb + rb) / 2;
        if (v[mid].first <= x)
            best = mid, lb = mid + 1;
        else
            rb = mid - 1;
    }
    return best;
}

struct aint_advanced {
    int n;
    vector <vector <pair <ll, int>>> seg;
    aint_advanced (int n) {
        this->n = n;
        seg.resize (1 + 4 * n);
    }
    void build (int node, int lb, int rb) {
        if (lb == rb) {
            seg[node] = v[lb];
            return;
        }
        int mid = (lb + rb) / 2, left_node = node * 2, right_node = node * 2 + 1;
        build (left_node, lb, mid);
        build (right_node, mid + 1, rb);
        seg[node].resize (seg[left_node].size () + seg[right_node].size ());
        merge (seg[left_node].begin (), seg[left_node].end (), seg[right_node].begin (), seg[right_node].end (), seg[node].begin ());
    }

    void query_range (int node, int lb, int rb, int x1, int x2, ll y1, ll y2, vector <int> &pairs) {
        if (x1 <= lb && rb <= x2) {
            int start = bin_search (seg[node], y1 - 1) + 1;
            int finish = bin_search (seg[node], y2);
            for (int i = start; i <= finish; i++)
                pairs.push_back (seg[node][i].second);
            return;
        }
        int mid = (lb + rb) / 2, left_node = node * 2, right_node = node * 2 + 1;
        if (x1 <= mid)
            query_range (left_node, lb, mid, x1, x2, y1, y2, pairs);
        if (mid < x2)
            query_range (right_node, mid + 1, rb, x1, x2, y1, y2, pairs);
    }
};
struct aint_simple {
    int n;
    vector <vector <pair <ll, int>>> seg;
    aint_simple (int n) {
        this->n = n;
        seg.resize (1 + 4 * n);
    }
    void build (int node, int lb, int rb) {
        if (lb == rb) {
            seg[node] = v[lb];
            return;
        }
        int mid = (lb + rb) / 2, left_node = node * 2, right_node = node * 2 + 1;
        build (left_node, lb, mid);
        build (right_node, mid + 1, rb);
        seg[node].resize (seg[left_node].size () + seg[right_node].size ());
        merge (seg[left_node].begin (), seg[left_node].end (), seg[right_node].begin (), seg[right_node].end (), seg[node].begin ());
    }

    ll query_range (int node, int lb, int rb, int x1, int x2, ll y1, ll y2) {
        if (x1 <= lb && rb <= x2) {
            int start = bin_search (seg[node], y1 - 1) + 1;
            int finish = bin_search (seg[node], y2);
            return finish - start + 1;
        }
        int mid = (lb + rb) / 2, left_node = node * 2, right_node = node * 2 + 1;
        ll ans = 0;
        if (x1 <= mid)
            ans += query_range (left_node, lb, mid, x1, x2, y1, y2);
        if (mid < x2)
            ans += query_range (right_node, mid + 1, rb, x1, x2, y1, y2);
        return ans;
    }
};
const int ERASE = 1, ADD = 0, QUERY = 2;
struct point_t {
    int x;
    int y;
};
vector <point_t> points;
struct event_t {
    int type;
    ll x1;
    ll x2;
    ll x;
    ll y;
    int idx;
    bool operator < (const event_t &other) const {
        if (y == other.y)
            return type < other.type;
        return y < other.y;
    }
};
int n;

ll distance (point_t a, point_t b) {
    return abs (a.x - b.x) + abs (a.y - b.y);
}
int k;

vector <point_t> true_points;

vector <ll> get_solution (ll max_distance) {
    map <ll, int> norm;
    for (int i = 0; i < n; i++) {
        ll x1 = points[i].x - max_distance, x2 = points[i].x + max_distance;
        norm[x1] = 0; norm[x2] = 0; norm[points[i].x] = 0;
    }
    int nr = 0;
    for (auto &x : norm)
        x.second = ++nr;
    aint_advanced vertical (nr);
    for (int i = 1; i <= nr; i++)
        v[i].clear ();
    for (int i = 0; i < n; i++)
        v[norm[points[i].x]].push_back ({points[i].y, i});
    for (int i = 1; i <= nr; i++)
        sort (v[i].begin (), v[i].end ());
    vertical.build (1, 1, nr);
    vector <ll> sol;
    for (int i = 0; i < n; i++) {
        ll x1 = points[i].x - max_distance;
        ll x2 = points[i].x + max_distance;
        ll y1 = points[i].y - max_distance;
        ll y2 = points[i].y + max_distance;
        x1 = norm[x1], x2 = norm[x2];
        vector <int> pairs;
        vertical.query_range (1, 1, nr, x1, x2, y1, y2, pairs);
        for (int it : pairs)
            if (it < i)
                sol.push_back (distance (true_points[i], true_points[it]));
    }
    sort (sol.begin (), sol.end ());
    return sol;
}
ll check (ll max_distance) {
     map <ll, int> norm;
    for (int i = 0; i < n; i++) {
        ll x1 = points[i].x - max_distance, x2 = points[i].x + max_distance;
        norm[x1] = 0; norm[x2] = 0; norm[points[i].x] = 0;
    }
    int nr = 0;
    for (auto &x : norm)
        x.second = ++nr;
    aint_simple vertical (nr);
    for (int i = 1; i <= nr; i++)
        v[i].clear ();
    for (int i = 0; i < n; i++)
        v[norm[points[i].x]].push_back ({points[i].y, i});
    for (int i = 1; i <= nr; i++)
        sort (v[i].begin (), v[i].end ());
    vertical.build (1, 1, nr);
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        ll x1 = points[i].x - max_distance;
        ll x2 = points[i].x + max_distance;
        ll y1 = points[i].y - max_distance;
        ll y2 = points[i].y + max_distance;
        x1 = norm[x1], x2 = norm[x2];
        ans += vertical.query_range (1, 1, nr, x1, x2, y1, y2) - 1;
    }
    return ans / 2;
}
int main () {
    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        true_points.push_back ({x, y});
        points.push_back ({x + y, x - y});
    }
    ll best = 0;
    ll lb = 0, rb = INF;
    while (lb <= rb) {
        ll mid = (lb + rb) / 2;
        if (check (mid) <= k)
            lb = mid + 1, best = mid;
        else
            rb = mid - 1;
    }
    vector <ll> sol = get_solution (best);
    while ((int) sol.size () > k)
        sol.pop_back ();
  //  dbg (best);
    for (ll x : sol)
        cout << x << "\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