oj.uz

Submission #992412

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

using namespace std;

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

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 67 ms 5072 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10015 ms 3484 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1413 ms 2388 KB Output is correct
2 Correct 1413 ms 2388 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1413 ms 2388 KB Output is correct
2 Correct 1413 ms 2388 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

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

Subtask #6
0 / 35.0

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