QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#113894 | #6639. Disk Tree | maspy | WA | 1ms | 3604kb | C++23 | 23.0kb | 2023-06-19 23:39:06 | 2023-06-19 23:39:08 |
Judging History
answer
#line 1 "library/my_template.hpp"
#if defined(LOCAL)
#include <my_template_compiled.hpp>
#else
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using u32 = unsigned int;
using u64 = unsigned long long;
using i128 = __int128;
template <class T>
constexpr T infty = 0;
template <>
constexpr int infty<int> = 1'000'000'000;
template <>
constexpr ll infty<ll> = ll(infty<int>) * infty<int> * 2;
template <>
constexpr u32 infty<u32> = infty<int>;
template <>
constexpr u64 infty<u64> = infty<ll>;
template <>
constexpr i128 infty<i128> = i128(infty<ll>) * infty<ll>;
template <>
constexpr double infty<double> = infty<ll>;
template <>
constexpr long double infty<long double> = infty<ll>;
using pi = pair<ll, ll>;
using vi = vector<ll>;
template <class T>
using vc = vector<T>;
template <class T>
using vvc = vector<vc<T>>;
template <class T>
using vvvc = vector<vvc<T>>;
template <class T>
using vvvvc = vector<vvvc<T>>;
template <class T>
using vvvvvc = vector<vvvvc<T>>;
template <class T>
using pq = priority_queue<T>;
template <class T>
using pqg = priority_queue<T, vector<T>, greater<T>>;
#define vv(type, name, h, ...) \
vector<vector<type>> name(h, vector<type>(__VA_ARGS__))
#define vvv(type, name, h, w, ...) \
vector<vector<vector<type>>> name( \
h, vector<vector<type>>(w, vector<type>(__VA_ARGS__)))
#define vvvv(type, name, a, b, c, ...) \
vector<vector<vector<vector<type>>>> name( \
a, vector<vector<vector<type>>>( \
b, vector<vector<type>>(c, vector<type>(__VA_ARGS__))))
// https://trap.jp/post/1224/
#define FOR1(a) for (ll _ = 0; _ < ll(a); ++_)
#define FOR2(i, a) for (ll i = 0; i < ll(a); ++i)
#define FOR3(i, a, b) for (ll i = a; i < ll(b); ++i)
#define FOR4(i, a, b, c) for (ll i = a; i < ll(b); i += (c))
#define FOR1_R(a) for (ll i = (a)-1; i >= ll(0); --i)
#define FOR2_R(i, a) for (ll i = (a)-1; i >= ll(0); --i)
#define FOR3_R(i, a, b) for (ll i = (b)-1; i >= ll(a); --i)
#define overload4(a, b, c, d, e, ...) e
#define overload3(a, b, c, d, ...) d
#define FOR(...) overload4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define FOR_R(...) overload3(__VA_ARGS__, FOR3_R, FOR2_R, FOR1_R)(__VA_ARGS__)
#define FOR_subset(t, s) \
for (ll t = (s); t >= 0; t = (t == 0 ? -1 : (t - 1) & (s)))
#define all(x) x.begin(), x.end()
#define len(x) ll(x.size())
#define elif else if
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define stoi stoll
int popcnt(int x) { return __builtin_popcount(x); }
int popcnt(u32 x) { return __builtin_popcount(x); }
int popcnt(ll x) { return __builtin_popcountll(x); }
int popcnt(u64 x) { return __builtin_popcountll(x); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 1, 2)
int topbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(u32 x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(ll x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
int topbit(u64 x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 0, 2)
int lowbit(int x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(u32 x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(ll x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }
int lowbit(u64 x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }
template <typename T, typename U>
T ceil(T x, U y) {
return (x > 0 ? (x + y - 1) / y : x / y);
}
template <typename T, typename U>
T floor(T x, U y) {
return (x > 0 ? x / y : (x - y + 1) / y);
}
template <typename T, typename U>
pair<T, T> divmod(T x, U y) {
T q = floor(x, y);
return {q, x - q * y};
}
template <typename T, typename U>
T SUM(const vector<U> &A) {
T sum = 0;
for (auto &&a: A) sum += a;
return sum;
}
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define LB(c, x) distance((c).begin(), lower_bound(all(c), (x)))
#define UB(c, x) distance((c).begin(), upper_bound(all(c), (x)))
#define UNIQUE(x) \
sort(all(x)), x.erase(unique(all(x)), x.end()), x.shrink_to_fit()
template <typename T>
T POP(deque<T> &que) {
T a = que.front();
que.pop_front();
return a;
}
template <typename T>
T POP(pq<T> &que) {
T a = que.top();
que.pop();
return a;
}
template <typename T>
T POP(pqg<T> &que) {
assert(!que.empty());
T a = que.top();
que.pop();
return a;
}
template <typename T>
T POP(vc<T> &que) {
assert(!que.empty());
T a = que.back();
que.pop_back();
return a;
}
template <typename F>
ll binary_search(F check, ll ok, ll ng, bool check_ok = true) {
if (check_ok) assert(check(ok));
while (abs(ok - ng) > 1) {
auto x = (ng + ok) / 2;
tie(ok, ng) = (check(x) ? mp(x, ng) : mp(ok, x));
}
return ok;
}
template <typename F>
double binary_search_real(F check, double ok, double ng, int iter = 100) {
FOR(iter) {
double x = (ok + ng) / 2;
tie(ok, ng) = (check(x) ? mp(x, ng) : mp(ok, x));
}
return (ok + ng) / 2;
}
template <class T, class S>
inline bool chmax(T &a, const S &b) {
return (a < b ? a = b, 1 : 0);
}
template <class T, class S>
inline bool chmin(T &a, const S &b) {
return (a > b ? a = b, 1 : 0);
}
// ? は -1
vc<int> s_to_vi(const string &S, char first_char) {
vc<int> A(S.size());
FOR(i, S.size()) { A[i] = (S[i] != '?' ? S[i] - first_char : -1); }
return A;
}
template <typename T, typename U>
vector<T> cumsum(vector<U> &A, int off = 1) {
int N = A.size();
vector<T> B(N + 1);
FOR(i, N) { B[i + 1] = B[i] + A[i]; }
if (off == 0) B.erase(B.begin());
return B;
}
// stable sort
template <typename T>
vector<int> argsort(const vector<T> &A) {
vector<int> ids(len(A));
iota(all(ids), 0);
sort(all(ids),
[&](int i, int j) { return (A[i] == A[j] ? i < j : A[i] < A[j]); });
return ids;
}
// A[I[0]], A[I[1]], ...
template <typename T>
vc<T> rearrange(const vc<T> &A, const vc<int> &I) {
vc<T> B(len(I));
FOR(i, len(I)) B[i] = A[I[i]];
return B;
}
#endif
#line 1 "library/other/io.hpp"
// based on yosupo's fastio
#include <unistd.h>
namespace fastio {
#define FASTIO
// クラスが read(), print() を持っているかを判定するメタ関数
struct has_write_impl {
template <class T>
static auto check(T &&x) -> decltype(x.write(), std::true_type{});
template <class T>
static auto check(...) -> std::false_type;
};
template <class T>
class has_write : public decltype(has_write_impl::check<T>(std::declval<T>())) {
};
struct has_read_impl {
template <class T>
static auto check(T &&x) -> decltype(x.read(), std::true_type{});
template <class T>
static auto check(...) -> std::false_type;
};
template <class T>
class has_read : public decltype(has_read_impl::check<T>(std::declval<T>())) {};
struct Scanner {
FILE *fp;
char line[(1 << 15) + 1];
size_t st = 0, ed = 0;
void reread() {
memmove(line, line + st, ed - st);
ed -= st;
st = 0;
ed += fread(line + ed, 1, (1 << 15) - ed, fp);
line[ed] = '\0';
}
bool succ() {
while (true) {
if (st == ed) {
reread();
if (st == ed) return false;
}
while (st != ed && isspace(line[st])) st++;
if (st != ed) break;
}
if (ed - st <= 50) {
bool sep = false;
for (size_t i = st; i < ed; i++) {
if (isspace(line[i])) {
sep = true;
break;
}
}
if (!sep) reread();
}
return true;
}
template <class T, enable_if_t<is_same<T, string>::value, int> = 0>
bool read_single(T &ref) {
if (!succ()) return false;
while (true) {
size_t sz = 0;
while (st + sz < ed && !isspace(line[st + sz])) sz++;
ref.append(line + st, sz);
st += sz;
if (!sz || st != ed) break;
reread();
}
return true;
}
template <class T, enable_if_t<is_integral<T>::value, int> = 0>
bool read_single(T &ref) {
if (!succ()) return false;
bool neg = false;
if (line[st] == '-') {
neg = true;
st++;
}
ref = T(0);
while (isdigit(line[st])) { ref = 10 * ref + (line[st++] & 0xf); }
if (neg) ref = -ref;
return true;
}
template <typename T,
typename enable_if<has_read<T>::value>::type * = nullptr>
inline bool read_single(T &x) {
x.read();
return true;
}
bool read_single(double &ref) {
string s;
if (!read_single(s)) return false;
ref = std::stod(s);
return true;
}
bool read_single(char &ref) {
string s;
if (!read_single(s) || s.size() != 1) return false;
ref = s[0];
return true;
}
template <class T>
bool read_single(vector<T> &ref) {
for (auto &d: ref) {
if (!read_single(d)) return false;
}
return true;
}
template <class T, class U>
bool read_single(pair<T, U> &p) {
return (read_single(p.first) && read_single(p.second));
}
template <size_t N = 0, typename T>
void read_single_tuple(T &t) {
if constexpr (N < std::tuple_size<T>::value) {
auto &x = std::get<N>(t);
read_single(x);
read_single_tuple<N + 1>(t);
}
}
template <class... T>
bool read_single(tuple<T...> &tpl) {
read_single_tuple(tpl);
return true;
}
void read() {}
template <class H, class... T>
void read(H &h, T &... t) {
bool f = read_single(h);
assert(f);
read(t...);
}
Scanner(FILE *fp) : fp(fp) {}
};
struct Printer {
Printer(FILE *_fp) : fp(_fp) {}
~Printer() { flush(); }
static constexpr size_t SIZE = 1 << 15;
FILE *fp;
char line[SIZE], small[50];
size_t pos = 0;
void flush() {
fwrite(line, 1, pos, fp);
pos = 0;
}
void write(const char val) {
if (pos == SIZE) flush();
line[pos++] = val;
}
template <class T, enable_if_t<is_integral<T>::value, int> = 0>
void write(T val) {
if (pos > (1 << 15) - 50) flush();
if (val == 0) {
write('0');
return;
}
if (val < 0) {
write('-');
val = -val; // todo min
}
size_t len = 0;
while (val) {
small[len++] = char(0x30 | (val % 10));
val /= 10;
}
for (size_t i = 0; i < len; i++) { line[pos + i] = small[len - 1 - i]; }
pos += len;
}
void write(const string s) {
for (char c: s) write(c);
}
void write(const char *s) {
size_t len = strlen(s);
for (size_t i = 0; i < len; i++) write(s[i]);
}
void write(const double x) {
ostringstream oss;
oss << fixed << setprecision(15) << x;
string s = oss.str();
write(s);
}
void write(const long double x) {
ostringstream oss;
oss << fixed << setprecision(15) << x;
string s = oss.str();
write(s);
}
template <typename T,
typename enable_if<has_write<T>::value>::type * = nullptr>
inline void write(T x) {
x.write();
}
template <class T>
void write(const vector<T> val) {
auto n = val.size();
for (size_t i = 0; i < n; i++) {
if (i) write(' ');
write(val[i]);
}
}
template <class T, class U>
void write(const pair<T, U> val) {
write(val.first);
write(' ');
write(val.second);
}
template <size_t N = 0, typename T>
void write_tuple(const T t) {
if constexpr (N < std::tuple_size<T>::value) {
if constexpr (N > 0) { write(' '); }
const auto x = std::get<N>(t);
write(x);
write_tuple<N + 1>(t);
}
}
template <class... T>
bool write(tuple<T...> tpl) {
write_tuple(tpl);
return true;
}
template <class T, size_t S>
void write(const array<T, S> val) {
auto n = val.size();
for (size_t i = 0; i < n; i++) {
if (i) write(' ');
write(val[i]);
}
}
void write(i128 val) {
string s;
bool negative = 0;
if (val < 0) {
negative = 1;
val = -val;
}
while (val) {
s += '0' + int(val % 10);
val /= 10;
}
if (negative) s += "-";
reverse(all(s));
if (len(s) == 0) s = "0";
write(s);
}
};
Scanner scanner = Scanner(stdin);
Printer printer = Printer(stdout);
void flush() { printer.flush(); }
void print() { printer.write('\n'); }
template <class Head, class... Tail>
void print(Head &&head, Tail &&... tail) {
printer.write(head);
if (sizeof...(Tail)) printer.write(' ');
print(forward<Tail>(tail)...);
}
void read() {}
template <class Head, class... Tail>
void read(Head &head, Tail &... tail) {
scanner.read(head);
read(tail...);
}
} // namespace fastio
using fastio::print;
using fastio::flush;
using fastio::read;
#define INT(...) \
int __VA_ARGS__; \
read(__VA_ARGS__)
#define LL(...) \
ll __VA_ARGS__; \
read(__VA_ARGS__)
#define STR(...) \
string __VA_ARGS__; \
read(__VA_ARGS__)
#define CHAR(...) \
char __VA_ARGS__; \
read(__VA_ARGS__)
#define DBL(...) \
double __VA_ARGS__; \
read(__VA_ARGS__)
#define VEC(type, name, size) \
vector<type> name(size); \
read(name)
#define VV(type, name, h, w) \
vector<vector<type>> name(h, vector<type>(w)); \
read(name)
void YES(bool t = 1) { print(t ? "YES" : "NO"); }
void NO(bool t = 1) { YES(!t); }
void Yes(bool t = 1) { print(t ? "Yes" : "No"); }
void No(bool t = 1) { Yes(!t); }
void yes(bool t = 1) { print(t ? "yes" : "no"); }
void no(bool t = 1) { yes(!t); }
#line 3 "main.cpp"
#line 1 "library/ds/fastset.hpp"
/* 64分木。
insert, erase
[]での存在判定
next, prev
*/
struct FastSet {
using uint = unsigned;
using ull = unsigned long long;
int bsr(ull x) { return 63 - __builtin_clzll(x); }
int bsf(ull x) { return __builtin_ctzll(x); }
static constexpr uint B = 64;
int n, lg;
vector<vector<ull>> seg;
FastSet(int _n) : n(_n) {
do {
seg.push_back(vector<ull>((_n + B - 1) / B));
_n = (_n + B - 1) / B;
} while (_n > 1);
lg = int(seg.size());
}
bool operator[](int i) const { return (seg[0][i / B] >> (i % B) & 1) != 0; }
void insert(int i) {
for (int h = 0; h < lg; h++) {
seg[h][i / B] |= 1ULL << (i % B);
i /= B;
}
}
void add(int i) { insert(i); }
void erase(int i) {
for (int h = 0; h < lg; h++) {
seg[h][i / B] &= ~(1ULL << (i % B));
if (seg[h][i / B]) break;
i /= B;
}
}
void remove(int i) { insert(i); }
// x以上最小の要素を返す。存在しなければ n。
int next(int i) {
chmax(i, 0);
if (i >= n) return n;
for (int h = 0; h < lg; h++) {
if (i / B == seg[h].size()) break;
ull d = seg[h][i / B] >> (i % B);
if (!d) {
i = i / B + 1;
continue;
}
// find
i += bsf(d);
for (int g = h - 1; g >= 0; g--) {
i *= B;
i += bsf(seg[g][i / B]);
}
return i;
}
return n;
}
// x以下最大の要素を返す。存在しなければ -1。
int prev(int i) {
if (i < 0) return -1;
if (i >= n) i = n - 1;
for (int h = 0; h < lg; h++) {
if (i == -1) break;
ull d = seg[h][i / B] << (63 - i % 64);
if (!d) {
i = i / B - 1;
continue;
}
// find
i += bsr(d) - (B - 1);
for (int g = h - 1; g >= 0; g--) {
i *= B;
i += bsr(seg[g][i / B]);
}
return i;
}
return -1;
}
// [l, r)
template <typename F>
void enumerate(int l, int r, F f) {
int x = l - 1;
while (1) {
x = next(x + 1);
if (x >= r) break;
f(x);
}
}
void debug() {
string s;
for (int i = 0; i < n; ++i) s += ((*this)[i] ? '1' : '0');
print(s);
}
};
#line 2 "library/ds/intervals.hpp"
// FastSet で高速化したもの
template <typename T>
struct Intervals_Fast {
const int LLIM, RLIM;
const T none_val;
// none_val でない区間の個数と長さ合計
int total_num;
int total_len;
vc<T> dat;
FastSet ss;
Intervals_Fast(int N, T none_val)
: LLIM(0),
RLIM(N),
none_val(none_val),
total_num(0),
total_len(0),
dat(N, none_val),
ss(N) {
ss.insert(0);
}
// x を含む区間の情報の取得
tuple<int, int, T> get(int x, bool ERASE) {
int l = ss.prev(x);
int r = ss.next(x + 1);
T t = dat[l];
if (t != none_val && ERASE) {
--total_num, total_len -= r - l;
dat[l] = none_val;
merge_at(l);
merge_at(r);
}
return {l, r, t};
}
// [L, R) 内の全データの取得
// f(l,r,x)
template <typename F>
void enumerate_range(int L, int R, F f, bool ERASE) {
assert(LLIM <= L && L <= R && R <= RLIM);
if (L == R) return;
if (!ERASE) {
int l = ss.prev(L);
while (l < R) {
int r = ss.next(l + 1);
f(max(l, L), min(r, R), dat[l]);
l = r;
}
return;
}
// 半端なところの分割
int p = ss.prev(L);
if (p < L) {
ss.insert(L);
dat[L] = dat[p];
if (dat[L] != none_val) ++total_num;
}
p = ss.next(R);
if (R < p) {
dat[R] = dat[ss.prev(R)];
ss.insert(R);
if (dat[R] != none_val) ++total_num;
}
p = L;
while (p < R) {
int q = ss.next(p + 1);
T x = dat[p];
f(p, q, x);
if (dat[p] != none_val) --total_num, total_len -= q - p;
ss.erase(p);
p = q;
}
ss.insert(L);
dat[L] = none_val;
}
void set(int L, int R, T t) {
if (L == R) return;
enumerate_range(
L, R, [](int l, int r, T x) -> void {}, true);
ss.insert(L);
dat[L] = t;
if (t != none_val) total_num++, total_len += R - L;
merge_at(L);
merge_at(R);
}
template <typename F>
void enumerate_all(F f) {
enumerate_range(0, RLIM, f, false);
}
void merge_at(int p) {
if (p <= 0 || RLIM <= p) return;
int q = ss.prev(p - 1);
if (dat[p] == dat[q]) {
if (dat[p] != none_val) --total_num;
ss.erase(p);
}
}
};
// https://codeforces.com/contest/1638/problem/E
// 持つ値のタイプ T、座標タイプ X
// コンストラクタでは T none_val を指定する
template <typename T, typename X = ll>
struct Intervals {
static constexpr X LLIM = -infty<X>;
static constexpr X RLIM = infty<X>;
const T none_val;
// none_val でない区間の個数と長さ合計
int total_num;
X total_len;
map<X, T> dat;
Intervals(T none_val) : none_val(none_val), total_num(0), total_len(0) {
dat[LLIM] = none_val;
dat[RLIM] = none_val;
}
// x を含む区間の情報の取得
tuple<X, X, T> get(X x, bool ERASE) {
auto it2 = dat.upper_bound(x);
auto it1 = prev(it2);
auto [l, tl] = *it1;
auto [r, tr] = *it2;
if (tl != none_val && ERASE) {
--total_num, total_len -= r - l;
dat[l] = none_val;
merge_at(l);
merge_at(r);
}
return {l, r, tl};
}
// [L, R) 内の全データの取得
template <typename F>
void enumerate_range(X L, X R, F f, bool ERASE) {
assert(LLIM <= L && L <= R && R <= RLIM);
if (!ERASE) {
auto it = prev(dat.upper_bound(L));
while ((*it).fi < R) {
auto it2 = next(it);
f(max((*it).fi, L), min((*it2).fi, R), (*it).se);
it = it2;
}
return;
}
// 半端なところの分割
auto p = prev(dat.upper_bound(L));
if ((*p).fi < L) {
dat[L] = (*p).se;
if (dat[L] != none_val) ++total_num;
}
p = dat.lower_bound(R);
if (R < (*p).fi) {
T t = (*prev(p)).se;
dat[R] = t;
if (t != none_val) ++total_num;
}
p = dat.lower_bound(L);
while (1) {
if ((*p).fi >= R) break;
auto q = next(p);
T t = (*p).se;
f((*p).fi, (*q).fi, t);
if (t != none_val) --total_num, total_len -= (*q).fi - (*p).fi;
p = dat.erase(p);
}
dat[L] = none_val;
}
void set(X L, X R, T t) {
enumerate_range(
L, R, [](int l, int r, T x) -> void {}, true);
dat[L] = t;
if (t != none_val) total_num++, total_len += R - L;
merge_at(L);
merge_at(R);
}
template <typename F>
void enumerate_all(F f) {
enumerate_range(LLIM, RLIM, f, false);
}
void merge_at(X p) {
if (p == LLIM || RLIM == p) return;
auto itp = dat.lower_bound(p);
assert((*itp).fi == p);
auto itq = prev(itp);
if ((*itp).se == (*itq).se) {
if ((*itp).se != none_val) --total_num;
dat.erase(itp);
}
}
};
#line 2 "library/ds/unionfind/unionfind.hpp"
struct UnionFind {
int n, n_comp;
vc<int> dat; // par or (-size)
UnionFind(int n = 0) { build(n); }
void build(int m) {
n = m, n_comp = m;
dat.assign(n, -1);
}
void reset() { build(n); }
int operator[](int x) {
while (dat[x] >= 0) {
int pp = dat[dat[x]];
if (pp < 0) { return dat[x]; }
x = dat[x] = pp;
}
return x;
}
ll size(int x) {
x = (*this)[x];
return -dat[x];
}
bool merge(int x, int y) {
x = (*this)[x], y = (*this)[y];
if (x == y) return false;
if (-dat[x] < -dat[y]) swap(x, y);
dat[x] += dat[y], dat[y] = x, n_comp--;
return true;
}
};
#line 6 "main.cpp"
void solve() {
LL(N);
vi X(N), Y(N), rad(N);
FOR(i, N) read(X[i]), read(Y[i]), read(rad[i]);
auto I = argsort(Y);
X = rearrange(X, I);
Y = rearrange(Y, I);
rad = rearrange(rad, I);
vi L(N), R(N);
FOR(i, N) L[i] = X[i] - rad[i], R[i] = X[i] + rad[i] + 1;
/*
・上下方向に結べるならば結ぶ
・各連結成分の左端の点と右端の点を見ると disjoint なはず
・右端と左端を結ぶと完成
*/
UnionFind uf(N);
vc<tuple<int, int, int, int>> ANS;
FOR(i, N) I[i] = i;
FOR(2) {
reverse(all(I));
Intervals<int, ll> dat(-1);
FOR(ord, N) {
int i = I[ord];
dat.enumerate_range(
L[i], R[i] + 1,
[&](int l, int r, int j) -> void {
if (j == -1) return;
if (uf.merge(i, j)) {
int x = max(l, 0);
ANS.eb(x, Y[j], x, Y[i]);
}
},
true);
dat.set(L[i], R[i] + 1, i);
}
}
// component -> {minx, mini, maxx, maxi}
using ARR = array<ll, 4>;
vc<ARR> dat(N);
FOR(i, N) { dat[i] = ARR{L[i], i, R[i], i}; }
FOR(i, N) {
int j = uf[i];
if (i == j) continue;
if (chmin(dat[j][0], L[i])) dat[j][1] = i;
if (chmax(dat[j][2], R[i])) dat[j][3] = i;
}
vc<int> V;
FOR(v, N) if (uf[v] == v) V.eb(v);
sort(all(V), [&](auto& a, auto& b) -> bool { return dat[a][0] < dat[b][0]; });
FOR(k, len(V) - 1) {
int i = V[k], j = V[k + 1];
i = dat[i][3], j = dat[j][1];
assert(X[i] + rad[i] < X[j] - rad[j]);
ANS.eb(X[i] + rad[i], Y[i], X[j] - rad[j], Y[j]);
}
assert(len(ANS) == N - 1);
YES();
for (auto&& x: ANS) print(x);
}
signed main() {
solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3504kb
input:
3 1 0 3 10 10 6 0 5 1
output:
YES 0 5 0 0 4 10 4 0
result:
ok answer = 1
Test #2:
score: 0
Accepted
time: 1ms
memory: 3496kb
input:
2 1 1 1 3 3 1
output:
YES 2 3 2 1
result:
ok answer = 1
Test #3:
score: 0
Accepted
time: 0ms
memory: 3464kb
input:
5 10 10 10 2 0 1 20 20 1 3 20 1 20 0 1
output:
YES 2 20 2 10 19 20 19 10 19 10 19 0 1 10 1 0
result:
ok answer = 1
Test #4:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
10 29 29 2 28 55 10 99 81 4 17 82 10 45 88 10 48 68 10 0 8 10 98 95 10 34 0 10 17 24 10
output:
YES 95 95 95 81 38 88 38 68 18 82 18 55 35 88 35 55 27 55 27 29 7 82 7 24 7 24 7 8 24 24 24 0 58 68 88 95
result:
ok answer = 1
Test #5:
score: -100
Wrong Answer
time: 1ms
memory: 3604kb
input:
100 490 783 12 666 460 55 561 245 6 223 323 25 3 520 77 225 161 24 514 190 16 997 914 100 412 265 100 374 610 36 296 854 39 601 901 2 307 21 100 390 422 24 940 414 32 332 438 35 553 992 100 235 775 3 656 901 37 770 417 22 649 305 100 448 84 3 375 939 77 910 847 9 776 357 37 743 97 100 371 502 39 508...
output:
YES 298 965 298 939 453 992 453 939 284 965 284 934 619 992 619 901 599 992 599 901 428 939 428 868 779 925 779 868 897 914 897 868 257 934 257 854 63 952 63 850 901 868 901 847 39 952 39 843 754 925 754 828 613 992 613 797 808 868 808 794 75 850 75 790 478 868 478 783 554 992 554 781 232 934 232 77...
result:
wrong answer Two line segments intersect, and it's not only the endpoints that intersect or line segments intersects/touches more than 2 disks