| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 682346 | vjudge1 | Road Construction (JOI21_road_construction) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
// #define int long long
#define ll long long
#define pb push_back
#define ppb pop_back
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define freopen(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);
const int N = 250000 + 5;
const int M = 1e3 + 5;
const ll mod = 1e9 + 7;
const ll inf = 1e17;
int n, k, x[N], y[N], id[N], cc;
vector<pair<int, int>> v;
int dist(int i, int j){
return abs(x[i] - x[j]) + abs(y[i] - y[j]);
}
int convert(int i, int j){
if(i < j) swap(i, j);
return i * (n + 1) + j;
}
multiset<int> st;
void solve(){
cin >> n >> k;
for(int i = 1; i <= n; i++){
cin >> x[i] >> y[i];
v.pb({x[i], y[i]});
}
sort(all(v));
cc = 70000000 / n;
for(int i = 1; i <= n; i++){
x[i] = v[i - 1].F;
y[i] = v[i - 1].S;
for(int j = max(1ll, i - cc); j < i; j++){
if(st.size() < k){
st.insert(dist(i, j));
}else{
auto to = st.end();
to--;
if(*to > dist(i, j)){
st.erase(to);
st.insert(dist(i, j));
}
}
}
}
while(k--){
cout << *(st.begin()) << '\n';
st.erase(st.begin());
}
//N * log() * const
}
main() {
fast
int tt = 1;
// cin >> tt;
while(tt--){
solve();
}
}