oj.uz

Submission #992343

# Submission time Handle Problem Language Result Execution time Memory
992343 2024-06-04T09:45:07 Z PVM_pvm Road Construction (JOI21_road_construction) C++17
100 / 100
 892 ms 15424 KB 
#include<bits/stdc++.h>
using namespace std;
#define MAXN 250007
#define int long long
struct point
{
    int x,y;
} arr[MAXN];
int n,k;
bool cmp1(point &a, point &b)
{
    if (a.x!=b.x) return a.x<b.x;
    return a.y<b.y;
}
bool cmp2(point &a, point &b)
{
    return a.y<b.y;
}
int dist(int a, int b)
{
    int xx=arr[a].x-arr[b].x;
    if (xx<0) xx*=-1;
    int yy=arr[a].y-arr[b].y;
    if (yy<0) yy*=-1;
    return xx+yy;
}
priority_queue<int> qu;
    int BSIZE=1000;
void check()
{
    for (int q=0;q<n;q++)
    {
        for (int w=1;w<=BSIZE;w++)
        {
            if (q-w<0) break;
            int dst=dist(q,q-w);
            if (qu.size()<k) qu.push(dst);
            else
            {
                if (dst<qu.top())
                {
                    qu.pop();
                    qu.push(dst);
                }
            }
        }
    }
}
signed main()
{
    cin>>n>>k;
    for (int q=0;q<n;q++) cin>>arr[q].x>>arr[q].y;
    sort(arr,arr+n,cmp1);
    check();
    //sort(arr,arr+n,cmp2);
    //check();
    vector<int> vv;
    while (!qu.empty())
    {
        vv.push_back(qu.top());
        qu.pop();
    }
    sort(vv.begin(),vv.end());
    for (int q=0;q<k;q++) cout<<vv[q]<<"\n";
}

Compilation message

road_construction.cpp: In function 'void check()':
road_construction.cpp:37:26: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   37 |             if (qu.size()<k) qu.push(dst);
      |                 ~~~~~~~~~^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 6972 KB Output is correct
2 Correct 67 ms 7016 KB Output is correct
3 Correct 57 ms 6984 KB Output is correct
4 Correct 50 ms 6976 KB Output is correct
5 Correct 70 ms 5948 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 786 ms 9532 KB Output is correct
2 Correct 792 ms 9536 KB Output is correct
3 Correct 48 ms 6972 KB Output is correct
4 Correct 756 ms 9276 KB Output is correct
5 Correct 689 ms 9792 KB Output is correct
6 Correct 697 ms 9628 KB Output is correct
7 Correct 740 ms 9244 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 601 ms 4176 KB Output is correct
2 Correct 590 ms 4320 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 550 ms 4192 KB Output is correct
5 Correct 606 ms 4172 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 601 ms 4176 KB Output is correct
2 Correct 590 ms 4320 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 550 ms 4192 KB Output is correct
5 Correct 606 ms 4172 KB Output is correct
6 Correct 604 ms 4180 KB Output is correct
7 Correct 574 ms 4176 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 590 ms 4188 KB Output is correct
11 Correct 555 ms 4176 KB Output is correct
12 Correct 610 ms 4180 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 6972 KB Output is correct
2 Correct 67 ms 7016 KB Output is correct
3 Correct 57 ms 6984 KB Output is correct
4 Correct 50 ms 6976 KB Output is correct
5 Correct 70 ms 5948 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 476 ms 8524 KB Output is correct
8 Correct 496 ms 10564 KB Output is correct
9 Correct 49 ms 6976 KB Output is correct
10 Correct 490 ms 9840 KB Output is correct
11 Correct 539 ms 9792 KB Output is correct
12 Correct 317 ms 10820 KB Output is correct
13 Correct 356 ms 9812 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 6972 KB Output is correct
2 Correct 67 ms 7016 KB Output is correct
3 Correct 57 ms 6984 KB Output is correct
4 Correct 50 ms 6976 KB Output is correct
5 Correct 70 ms 5948 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 786 ms 9532 KB Output is correct
8 Correct 792 ms 9536 KB Output is correct
9 Correct 48 ms 6972 KB Output is correct
10 Correct 756 ms 9276 KB Output is correct
11 Correct 689 ms 9792 KB Output is correct
12 Correct 697 ms 9628 KB Output is correct
13 Correct 740 ms 9244 KB Output is correct
14 Correct 601 ms 4176 KB Output is correct
15 Correct 590 ms 4320 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 550 ms 4192 KB Output is correct
18 Correct 606 ms 4172 KB Output is correct
19 Correct 604 ms 4180 KB Output is correct
20 Correct 574 ms 4176 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 590 ms 4188 KB Output is correct
24 Correct 555 ms 4176 KB Output is correct
25 Correct 610 ms 4180 KB Output is correct
26 Correct 476 ms 8524 KB Output is correct
27 Correct 496 ms 10564 KB Output is correct
28 Correct 49 ms 6976 KB Output is correct
29 Correct 490 ms 9840 KB Output is correct
30 Correct 539 ms 9792 KB Output is correct
31 Correct 317 ms 10820 KB Output is correct
32 Correct 356 ms 9812 KB Output is correct
33 Correct 892 ms 15420 KB Output is correct
34 Correct 791 ms 15420 KB Output is correct
35 Correct 826 ms 14660 KB Output is correct
36 Correct 641 ms 15424 KB Output is correct
37 Correct 743 ms 15364 KB Output is correct
38 Correct 745 ms 14784 KB Output is correct