#pragma GCC optimize("Ofast")
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cwchar>
#include <cwctype>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <codecvt>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
using namespace std;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
const int MAXN = 2.5e5 + 10;
const int MOD = 1e9 + 7;
#define int long long
int rnd(int x, int y) {
int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
struct node{
int val, idx;
} a[4*MAXN];
void init(int l, int r, int idx) {
if(l == r) {
a[idx].val = 0;
a[idx].idx = l;
return;
}
int mid = (l + r) >> 1;
init(l, mid, 2*idx + 1);
init(mid+1, r, 2*idx + 2);
}
void u(int l, int r, int tar, int idx, int val) {
if(l == r) {
a[idx].val = val;
return;
}
int mid = (l + r) >> 1;
if(tar <= mid) u(l, mid, tar, 2*idx+1, val);
else u(mid+1, r, tar, 2*idx+2, val);
a[idx].val = min(a[2*idx+1].val, a[2*idx+2].val);
a[idx].idx = (a[2*idx+1].val <= a[2*idx+2].val ? a[2*idx+1].idx : a[2*idx+2].idx);
}
pair<int, int> qu(int l, int r, int constl, int constr, int idx) {
if(l<=constl && constr<=r) return {a[idx].val, a[idx].idx};
int mid = (constl+constr) >> 1;
if(mid<l || r<constl) return qu(l, r, mid+1, constr, 2*idx+2);
else if(constr<l || r<mid+1) return qu(l, r, constl, mid, 2*idx+1);
return min(qu(l, r, constl, mid, 2*idx+1), qu(l, r, mid+1, constr, 2*idx+2));
}
int n, k, x[MAXN], y[MAXN];
void update(int i, int v) {
u(1, n-1, i, 0, v);
}
int nxt[MAXN];
int query(int l, int r) {
pair<int, int> res = qu(l, r, 1, n-1, 0);
nxt[res.second]++;
if(nxt[res.second] > n) {
update(res.second, (int)1e18);
}
else {
update(res.second, x[nxt[res.second]] - x[res.second]);
}
return res.first;
}
bool cmp1(int a, int b) {
return x[a] - y[a] < x[b] - y[b];
}
bool cmp2(int a, int b) {
return x[a] + y[a] < x[b] + y[b];
}
void solve(int tc) {
/*
cin >> n >> k;
for(int i=1; i<=n; i++) {
cin >> x[i] >> y[i];
}
*/
n = rnd(1001, 2000);
k = rnd(2, 10);
for(int i=1; i<=n; i++) {
x[i] = rnd(1, 10000);
y[i] = rnd(1, 10000);
}
if(n <= 1000) {
vector<int> v;
for(int i=1; i<=n; i++) {
for(int j=i+1; j<=n; j++) {
v.push_back(abs(x[i] - x[j]) + abs(y[i] - y[j]));
}
}
sort(v.begin(), v.end());
for(int i=0; i<k; i++) cout << v[i] << "\n";
return;
}
bool yes = 1;
for(int i=1; i<=n; i++) yes &= (y[i] == 0);
if(yes) {
for(int i=1; i<=n; i++) nxt[i] = i + 1;
init(1, n-1, 0);
sort(x+1, x+n+1);
for(int i=1; i<n; i++) update(i, x[i+1] - x[i]);
for(int i=0; i<k; i++) cout << query(1, n-1) << "\n";
return;
}
int p[n+1];
for(int i=1; i<=n; i++) p[i] = i;
priority_queue<int> pq;
sort(p+1, p+n+1, cmp1);
for(int i=1; i<=n; i++) {
for(int j=1; j<=100 && i+j <= n; j++) {
pq.push(abs(x[p[i+j]] - x[p[i]]) + abs(y[p[i+j]] - y[p[i]]));
if(pq.size() > k) pq.pop();
}
}
sort(p+1, p+n+1, cmp2);
for(int i=1; i<=n; i++) {
for(int j=1; j<=100 && i+j <= n; j++) {
pq.push(abs(x[p[i+j]] - x[p[i]]) + abs(y[p[i+j]] - y[p[i]]));
if(pq.size() > k) pq.pop();
}
}
stack<int> st;
while(pq.size()) {
st.push(pq.top()); pq.pop();
}
while(st.size()) {
cout << st.top() << "\n"; st.pop();
}
}
int32_t main(){
ios::sync_with_stdio(0); cin.tie(0);
int t = 1; //cin >> t;
for(int i=1; i<=t; i++) solve(i);
}
Compilation message
road_construction.cpp: In function 'void solve(long long int)':
road_construction.cpp:184:20: 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]
184 | if(pq.size() > k) pq.pop();
| ~~~~~~~~~~^~~
road_construction.cpp:191:20: 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]
191 | if(pq.size() > k) pq.pop();
| ~~~~~~~~~~^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
7 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
4 ms |
372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
4 ms |
372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
