This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
typedef long long ll;
#define fi first
#define se second
#define pll pair<ll,ll>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl;
#define MP make_pair
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define SZ(x) (ll)x.size()
#define ALL(x) x.begin(),x.end()
#define endl "\n"
const ll inf=1e18;
ll lowbit(ll x){return x&(-x);}
const ll maxn=255555;
ll x[maxn],y[maxn];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
ll n,k;cin>>n>>k;
rep(i,1,n+1)cin>>x[i]>>y[i];
sort(x+1,x+n+1);
multiset<pair<ll,pll>>s;
rep(i,1,n){
s.insert(MP(x[i+1]-x[i],MP(i,i+1)));
}
vector<ll>ans;
while(ans.size()<k){
auto tmp=*s.begin();
ans.pb(tmp.fi);
ll l=tmp.se.fi,r=tmp.se.se;
s.erase(tmp);
if(r<n){
s.insert(MP(x[r+1]-x[l],MP(l,r+1)));
}
}
for(auto w:ans)cout<<w<<endl;
return 0;
}
Compilation message (stderr)
road_construction.cpp: In function 'int main()':
road_construction.cpp:34:18: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
34 | while(ans.size()<k){
| ~~~~~~~~~~^~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |