Submission #992418

#	Time	Username	Problem	Language	Result	Execution time	Memory
992418		borisAngelov	Road Construction (JOI21_road_construction)	C++17	100 / 100	665 ms	14536 KiB

road_construction

#include <bits/stdc++.h>

using namespace std;

const int maxn = 250005;
const int block = 1000;

int n, k;
priority_queue<long long> pq;
pair<long long, long long> a[maxn];

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    cin >> n >> k;

    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i].first >> a[i].second;
    }

    sort(a + 1, a + n + 1);

    /*for (int i = 1; i <= n; ++i)
    {
        cout << a[i].first << " " << a[i].second << "\n";
    }*/

    for (int i = 1; i <= n; ++i)
    {
        int upTo = max(1, i - block);
        long long dist;

        for (int j = i - 1; j >= upTo; --j)
        {
            dist = a[i].first - a[j].first + abs(a[i].second - a[j].second);

            //cout << i << " :: " << j << " -> " << dist << endl;

            if (pq.size() < k)
            {
                pq.push(dist);
            }
            else if (dist < pq.top())
            {
                pq.push(dist);
                pq.pop();
            }
        }
    }

    stack<long long> ans;

    while (!pq.empty())
    {
        ans.push(pq.top());
        pq.pop();
    }

    while (!ans.empty())
    {
        cout << ans.top() << "\n";
        ans.pop();
    }

    return 0;
}

Compilation message (stderr)

road_construction.cpp: In function 'int main()':
road_construction.cpp:48:27: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   48 |             if (pq.size() < k)
      |                 ~~~~~~~~~~^~~

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