oj.uz

Submission #992415

# Submission time Handle Problem Language Result Execution time Memory
992415 2024-06-04T12:19:07 Z borisAngelov Road Construction (JOI21_road_construction) C++17
27 / 100
 427 ms 9672 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 250005;
const int block = 500;

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

# Verdict Execution time Memory Grader output
1 Incorrect 57 ms 6856 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 427 ms 9520 KB Output is correct
2 Correct 426 ms 9672 KB Output is correct
3 Incorrect 37 ms 6340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 4180 KB Output is correct
2 Correct 226 ms 4220 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 205 ms 6908 KB Output is correct
5 Correct 253 ms 8596 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 4180 KB Output is correct
2 Correct 226 ms 4220 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 205 ms 6908 KB Output is correct
5 Correct 253 ms 8596 KB Output is correct
6 Correct 219 ms 8272 KB Output is correct
7 Correct 232 ms 8276 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 223 ms 8276 KB Output is correct
11 Correct 204 ms 6744 KB Output is correct
12 Correct 226 ms 8568 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 57 ms 6856 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 57 ms 6856 KB Output isn't correct
2 Halted 0 ms 0 KB -