oj.uz

Submission #992418

# Submission time Handle Problem Language Result Execution time Memory
992418 2024-06-04T12:19:36 Z borisAngelov Road Construction (JOI21_road_construction) C++17
100 / 100
 665 ms 14536 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 6856 KB Output is correct
2 Correct 61 ms 6852 KB Output is correct
3 Correct 52 ms 7112 KB Output is correct
4 Correct 52 ms 7112 KB Output is correct
5 Correct 65 ms 5932 KB Output is correct
6 Correct 2 ms 348 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 641 ms 9416 KB Output is correct
2 Correct 636 ms 9568 KB Output is correct
3 Correct 46 ms 6896 KB Output is correct
4 Correct 580 ms 11832 KB Output is correct
5 Correct 503 ms 11988 KB Output is correct
6 Correct 499 ms 11976 KB Output is correct
7 Correct 492 ms 11628 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 394 ms 4348 KB Output is correct
2 Correct 395 ms 4188 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 370 ms 4344 KB Output is correct
5 Correct 380 ms 4176 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 394 ms 4348 KB Output is correct
2 Correct 395 ms 4188 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 370 ms 4344 KB Output is correct
5 Correct 380 ms 4176 KB Output is correct
6 Correct 378 ms 4180 KB Output is correct
7 Correct 377 ms 4516 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 600 KB Output is correct
10 Correct 418 ms 4152 KB Output is correct
11 Correct 374 ms 4436 KB Output is correct
12 Correct 383 ms 4176 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 6856 KB Output is correct
2 Correct 61 ms 6852 KB Output is correct
3 Correct 52 ms 7112 KB Output is correct
4 Correct 52 ms 7112 KB Output is correct
5 Correct 65 ms 5932 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 401 ms 10400 KB Output is correct
8 Correct 390 ms 10436 KB Output is correct
9 Correct 47 ms 7108 KB Output is correct
10 Correct 397 ms 9636 KB Output is correct
11 Correct 456 ms 9632 KB Output is correct
12 Correct 235 ms 10436 KB Output is correct
13 Correct 275 ms 9128 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 6856 KB Output is correct
2 Correct 61 ms 6852 KB Output is correct
3 Correct 52 ms 7112 KB Output is correct
4 Correct 52 ms 7112 KB Output is correct
5 Correct 65 ms 5932 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 641 ms 9416 KB Output is correct
8 Correct 636 ms 9568 KB Output is correct
9 Correct 46 ms 6896 KB Output is correct
10 Correct 580 ms 11832 KB Output is correct
11 Correct 503 ms 11988 KB Output is correct
12 Correct 499 ms 11976 KB Output is correct
13 Correct 492 ms 11628 KB Output is correct
14 Correct 394 ms 4348 KB Output is correct
15 Correct 395 ms 4188 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 370 ms 4344 KB Output is correct
18 Correct 380 ms 4176 KB Output is correct
19 Correct 378 ms 4180 KB Output is correct
20 Correct 377 ms 4516 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Correct 0 ms 600 KB Output is correct
23 Correct 418 ms 4152 KB Output is correct
24 Correct 374 ms 4436 KB Output is correct
25 Correct 383 ms 4176 KB Output is correct
26 Correct 401 ms 10400 KB Output is correct
27 Correct 390 ms 10436 KB Output is correct
28 Correct 47 ms 7108 KB Output is correct
29 Correct 397 ms 9636 KB Output is correct
30 Correct 456 ms 9632 KB Output is correct
31 Correct 235 ms 10436 KB Output is correct
32 Correct 275 ms 9128 KB Output is correct
33 Correct 665 ms 14384 KB Output is correct
34 Correct 664 ms 14536 KB Output is correct
35 Correct 644 ms 13508 KB Output is correct
36 Correct 457 ms 14244 KB Output is correct
37 Correct 494 ms 14412 KB Output is correct
38 Correct 524 ms 13108 KB Output is correct