#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();
}
}
Compilation message
road_construction.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
3 | #pragma GCC optimization("O3")
|
road_construction.cpp:4: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
4 | #pragma GCC optimization("unroll-loops")
|
road_construction.cpp:5: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
5 | #pragma comment(linker, "/stack:200000000")
|
road_construction.cpp: In function 'void solve()':
road_construction.cpp:51:26: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
51 | if(st.size() < k){
| ~~~~~~~~~~^~~
road_construction.cpp: At global scope:
road_construction.cpp:72:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
72 | main() {
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
213 ms |
14668 KB |
Output is correct |
2 |
Correct |
205 ms |
14572 KB |
Output is correct |
3 |
Correct |
155 ms |
14704 KB |
Output is correct |
4 |
Correct |
135 ms |
14764 KB |
Output is correct |
5 |
Correct |
207 ms |
13500 KB |
Output is correct |
6 |
Correct |
3 ms |
468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1300 ms |
21028 KB |
Output is correct |
2 |
Correct |
1422 ms |
21072 KB |
Output is correct |
3 |
Correct |
108 ms |
14616 KB |
Output is correct |
4 |
Incorrect |
1000 ms |
20924 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
270 ms |
8236 KB |
Output is correct |
2 |
Correct |
264 ms |
8176 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
251 ms |
8164 KB |
Output is correct |
5 |
Correct |
256 ms |
8192 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
270 ms |
8236 KB |
Output is correct |
2 |
Correct |
264 ms |
8176 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
251 ms |
8164 KB |
Output is correct |
5 |
Correct |
256 ms |
8192 KB |
Output is correct |
6 |
Correct |
271 ms |
8400 KB |
Output is correct |
7 |
Correct |
258 ms |
8168 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
307 ms |
8224 KB |
Output is correct |
11 |
Correct |
243 ms |
8236 KB |
Output is correct |
12 |
Correct |
263 ms |
8156 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
213 ms |
14668 KB |
Output is correct |
2 |
Correct |
205 ms |
14572 KB |
Output is correct |
3 |
Correct |
155 ms |
14704 KB |
Output is correct |
4 |
Correct |
135 ms |
14764 KB |
Output is correct |
5 |
Correct |
207 ms |
13500 KB |
Output is correct |
6 |
Correct |
3 ms |
468 KB |
Output is correct |
7 |
Correct |
1416 ms |
17132 KB |
Output is correct |
8 |
Correct |
1434 ms |
19288 KB |
Output is correct |
9 |
Correct |
130 ms |
14876 KB |
Output is correct |
10 |
Incorrect |
1502 ms |
18636 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
213 ms |
14668 KB |
Output is correct |
2 |
Correct |
205 ms |
14572 KB |
Output is correct |
3 |
Correct |
155 ms |
14704 KB |
Output is correct |
4 |
Correct |
135 ms |
14764 KB |
Output is correct |
5 |
Correct |
207 ms |
13500 KB |
Output is correct |
6 |
Correct |
3 ms |
468 KB |
Output is correct |
7 |
Correct |
1300 ms |
21028 KB |
Output is correct |
8 |
Correct |
1422 ms |
21072 KB |
Output is correct |
9 |
Correct |
108 ms |
14616 KB |
Output is correct |
10 |
Incorrect |
1000 ms |
20924 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |