Submission #992343

#TimeUsernameProblemLanguageResultExecution timeMemory
992343PVM_pvmRoad Construction (JOI21_road_construction)C++17
100 / 100
892 ms15424 KiB
#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 (stderr)

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);
      |                 ~~~~~~~~~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...