Submission #1292590

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292590		NValchanov	Road Construction (JOI21_road_construction)	C++20	100 / 100	1626 ms	10324 KiB

road_construction

#include <iostream>
#include <set>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

typedef long long llong;

const int MAXN = 3e5 + 10;
const llong MAXD = 4e9 + 10;

int n, k;
pair < llong, llong > points[MAXN];

void read()
{
    cin >> n >> k;

    for(int i = 1; i <= n; i++)
    {
        llong x, y;
        cin >> x >> y;

        points[i] = {x + y, x - y};
    }

    sort(points + 1, points + 1 + n);
}

vector < llong > check(llong d)
{
    set < pair < llong, llong > > s;
    queue < pair < llong, llong > > q;
    
    vector < llong > result;

    for(int i = 1; i <= n; i++)
    {
        while(!q.empty() && q.front().first < points[i].first - d)
        {
            s.erase({q.front().second, q.front().first});
            q.pop();
        }

        auto beg = s.lower_bound({points[i].second - d, -MAXD});

        for(auto it = beg; it != s.end(); it++)
        {
            if(it->first > points[i].second + d)
                break;

            result.push_back(max(llabs(points[i].first - it->second), llabs(points[i].second - it->first)));
        }

        if(result.size() >= k)
            return result;

        s.insert({points[i].second, points[i].first});
        q.push({points[i].first, points[i].second});
    }

    return result;
}

void solve()
{
    llong left = 0;
    llong right = MAXD;
    llong mid;

    while(right - left > 1)
    {
        mid = left + (right - left) / 2;

        if(check(mid).size() >= k)
            right = mid;
        else
            left = mid;
    }

    vector < llong > v = check(right - 1);

    sort(v.begin(), v.end());

    for(llong d : v)
    {
        cout << d << '\n';
    }

    for(int i = 1; i <= k - v.size(); i++)
    {
        cout << right << '\n';
    }
}

int main()
{
    read();
    solve();

    return 0;
}

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