oj.uz

Submission #992410

# Submission time Handle Problem Language Result Execution time Memory
992410 2024-06-04T12:16:34 Z borisAngelov Road Construction (JOI21_road_construction) C++17
0 / 100
 6371 ms 8140 KB 
#include <bits/stdc++.h>

using namespace std;

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

int n, k;
priority_queue<int> pq;
pair<int, int> 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), 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;

            pq.push(dist);

            if (pq.size() > k)
            {
                pq.pop();
            }
        }
    }

    stack<int> 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:49:27: warning: comparison of integer expressions of different signedness: 'std::priority_queue<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   49 |             if (pq.size() > k)
      |                 ~~~~~~~~~~^~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6371 ms 8140 KB Output is correct
2 Correct 6293 ms 8124 KB Output is correct
3 Incorrect 38 ms 4560 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 747 ms 6484 KB Output is correct
2 Correct 758 ms 6484 KB Output is correct
3 Incorrect 0 ms 344 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 747 ms 6484 KB Output is correct
2 Correct 758 ms 6484 KB Output is correct
3 Incorrect 0 ms 344 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

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

Subtask #6
0 / 35.0

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