Submission #825895

#	Time	Username	Problem	Language	Result	Execution time	Memory
825895		xink	Road Construction (JOI21_road_construction)	C++14	100 / 100	1827 ms	18252 KiB

road_construction

#include <iostream>
#include <vector>
#include <utility>
#include <sstream>
#include <climits>
#include <cstring>
#include <math.h>
#include <algorithm>
#include <assert.h>
#include <set>
#define ll long long
#define ld long double
using namespace std;
const ll mod = 1e9 + 7;
typedef vector<int> vi;
typedef pair<ll, ll> ii;
typedef pair<ii, int> pii;
typedef vector<ii> vii;
const int maxn1 = 3e5 + 5, maxn2 = 1e6 + 6;
ii coor[maxn1];
ll dist[maxn2];
struct cmp
{
    bool operator()(const ii &a, const ii &b) const
    {
        if (a.second == b.second)
            return a.first < b.first;
        return a.second < b.second;
    }
};

set<ii, cmp> s;

ll get_manhattan_dist(int i, int j)
{
    return abs(coor[i].first - coor[j].first) + abs(coor[i].second - coor[j].second);
}

ll get_manhattan_dist(ii p1, ii p2)
{
    return abs(p1.first - p2.first) + abs(p1.second - p2.second);
}

void solve_sub1(int n, int k)
{
    int n_road = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < i; j++)
        {
            dist[n_road++] = get_manhattan_dist(i, j);
        }
    }
    sort(dist, dist + n_road);
    for (int i = 0; i < k; i++)
    {
        cout << dist[i] << "\n";
    }
}

void solve_sub2(int n, ll k)
{
    sort(coor, coor + n);
    ll l = 1, r = coor[n - 1].first - coor[0].first;
    while (l < r)
    {
        int m = (l + r) >> 1, l1 = 0;
        ll cnt = 0;
        for (int i = 0; i < n; i++)
        {
            while (l1 < i && get_manhattan_dist(l1, i) > m)
            {
                l1++;
            }
            cnt += i - l1;
        }
        if (cnt >= k)
        {
            r = m;
        }
        else
        {
            l = m + 1;
        }
    }
    int n_road = 0, lp = 0;
    for (int i = 0; i < n; i++)
    {
        while (lp < i && get_manhattan_dist(lp, i) >= l)
        {
            lp++;
        }
        for (int j = lp; j < i; j++)
        {
            dist[n_road++] = get_manhattan_dist(j, i);
        }
    }
    for (int i = n_road; i < k; i++)
    {
        dist[i] = l;
    }
    sort(dist, dist + k);
    for (int i = 0; i < k; i++)
    {
        cout << dist[i] << '\n';
    }
}

bool check_enough(int n, ll k, ll m)
{
    s.clear();
    ll cnt = 0;
    for (int i = 0; i < n; i++)
    {
        ii curr_p = {-1e10, coor[i].second - m};
        while (true)
        {
            set<ii>::iterator it1 = s.upper_bound(curr_p);
            if (it1 == s.end())
                break;
            curr_p = *it1;
            if (curr_p.second > coor[i].second + m)
                break;

            if (curr_p.first < coor[i].first - m)
            {
                s.erase(it1);
                continue;
            }

            if (get_manhattan_dist(curr_p, coor[i]) <= m)
            {
                cnt++;
                if (cnt >= k)
                    return true;
            }
        }
        s.insert(coor[i]);
    }
    return false;
}

void create_dist(int n, ll k, ll l)
{
    s.clear();
    ll n_road = 0;
    for (int i = 0; i < n; i++)
    {
        ii curr_p = {-1e10, coor[i].second - l};
        while (true)
        {
            set<ii>::iterator it1 = s.upper_bound(curr_p);
            if (it1 == s.end())
                break;
            curr_p = *it1;
            if (curr_p.second > coor[i].second + l)
                break;

            if (curr_p.first < coor[i].first - l)
            {
                s.erase(it1);
                continue;
            }

            if (get_manhattan_dist(curr_p, coor[i]) < l)
            {
                dist[n_road++] = get_manhattan_dist(curr_p, coor[i]);
            }
        }
        s.insert(coor[i]);
    }
    for (int i = n_road; i < k; i++)
    {
        dist[i] = l;
    }
    sort(dist, dist + k);
    for (int i = 0; i < k; i++)
    {
        cout << dist[i] << "\n";
    }
}

void solve_sub3(int n, int k)
{
    sort(coor, coor + n);
    ll l = 1, r = 1e10;
    while (l < r)
    {
        int m = (l + r) >> 1;
        if (check_enough(n, k, m))
        {
            r = m;
        }
        else
        {
            l = m + 1;
        }
    }
    create_dist(n, k, l);
}

void solve()
{
    int n, k;
    cin >> n >> k;
    bool all_y0 = 1;
    for (int i = 0; i < n; i++)
    {
        cin >> coor[i].first >> coor[i].second;
        all_y0 &= (coor[i].second == 0);
    }
    if (n <= 1000)
    {
        solve_sub1(n, k);
        return;
    }
    if (all_y0)
    {
        solve_sub2(n, k);
        return;
    }
    solve_sub3(n, k);
}

int main()
{
    // freopen("input_text", "r", stdin);
    // freopen("output_text", "w", stdout);
    // ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t-- > 0)
        solve();
}

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