#line 1 "C.cpp" #include #include #include #include #include #line 1 "~/git/library/utility/io.cpp" /** * @brief 入出力 * @author えびちゃん */ #include #include #include #include #include #line 15 "~/git/library/utility/io.cpp" class format { public: using size_type = size_t; private: char const* M_fmt; size_type M_nvars = 0; size_type M_error = -1; void M_print(std::ostream& os, char const* pos) const { while (*pos) { if (*pos == '{' || *pos == '}') ++pos; os << *pos++; } } template void M_print(std::ostream& os, char const* pos, Tp const& x, Args const&... xs) const { while (true) { if (*pos == '{') { if (pos[1] == '{') { ++pos; os << '{'; } else { char const* next = M_print_formatted(os, pos, x); return M_print(os, next, xs...); } } else { if (*pos == '}') ++pos; os << *pos; } ++pos; } char const* next = M_print_formatted(os, pos, x); M_print(os, next, xs...); } template char const* M_print_formatted(std::ostream& os, char const* pos, Tp const& x) const { // parse flags, preferably while (*++pos != '}') {} os << x; return ++pos; } void M_scan(std::istream& is, char const* pos) const { while (true) { if (*pos == '{' || *pos == '}') ++pos; if (isspace(*pos)) { while (isspace(is.peek())) is.get(); } else { if (is.peek() == *pos) { ++pos; is.get(); } else { return; } } } } template void M_scan(std::istream& is, char const* pos, Tp& x, Args&&... xs) const { while (true) { if (*pos == '{') { if (pos[1] == '{') { if (is.peek() == '{') { ++pos; is.get(); } else { return; } } else { char const* next = M_scan_formatted(is, pos, x); return M_scan(is, next, xs...); } } else if (isspace(*pos)) { while (isspace(is.peek())) is.get(); ++pos; } else { if (*pos == '}') ++pos; if (is.peek() == *pos) { ++pos; is.get(); } else { return; } } } } template char const* M_scan_formatted(std::istream& is, char const* pos, Tp& x) const { // parse flags, preferably while (*++pos != '}') {} is >> x; return ++pos; } public: constexpr format(char const* fmt): M_fmt(fmt) { bool opens = 0; size_type i = 0; for (; fmt[i]; ++i) { if (fmt[i] == '{') { if (fmt[i+1] == '{') { ++i; continue; } // escaped if (opens) { M_error = i; return; } opens = true; } else if (fmt[i] == '}') { if (fmt[i+1] == '}') { ++i; continue; } // escaped if (!opens) { M_error = i; return; } opens = false; ++M_nvars; } } if (opens) { M_error = i; return; } } template void print_(std::ostream& os, Args const&... xs) const { M_print(os, M_fmt, xs...); } template void scan_(std::istream& is, Args&&... xs) const { M_scan(is, M_fmt, xs...); } constexpr size_type count() const { return M_nvars; } constexpr size_type error() const { return M_error; } }; #define VA_COUNT(...) \ std::tuple_size::value #define fprint(os, fmt, ...) (void)({ \ constexpr format fmt_(fmt); \ constexpr size_t lhs = fmt_.count(); \ constexpr size_t rhs = VA_COUNT(__VA_ARGS__); \ static_assert(lhs == rhs, "size mismatch"); \ static_assert(fmt_.error()+1 == 0, "misformatted"); \ fmt_.print_(os, ##__VA_ARGS__); \ }) #define fprintln(os, fmt, ...) (void)({ \ fprint(os, fmt, ##__VA_ARGS__); \ os << '\n';; \ }) #define print(...) fprint(std::cout, ##__VA_ARGS__) #define println(...) fprintln(std::cout, ##__VA_ARGS__) #define eprint(...) fprint(std::cerr, ##__VA_ARGS__) #define eprintln(...) fprintln(std::cerr, ##__VA_ARGS__) #define fscan(is, fmt, ...) (void)({ \ constexpr format fmt_(fmt); \ constexpr size_t lhs = fmt_.count(); \ constexpr size_t rhs = VA_COUNT(__VA_ARGS__); \ static_assert(lhs == rhs, "size mismatch"); \ static_assert(fmt_.error()+1 == 0, "misformatted"); \ fmt_.scan_(is, ##__VA_ARGS__); \ }) #define scan(...) fscan(std::cin, __VA_ARGS__) __attribute__((constructor)) void ioinit() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cerr.tie(nullptr); std::cout << std::fixed << std::setprecision(16); } #line 1 "~/git/library/utility/make/vector.cpp" /** * @brief 多次元 vector の作成 * @author えびちゃん */ #line 10 "~/git/library/utility/make/vector.cpp" #include #include namespace detail { template auto make_vector(std::vector& sizes, Tp const& x) { if constexpr (Nb == 1) { return std::vector(sizes[0], x); } else { size_t size = sizes[Nb-1]; sizes.pop_back(); return std::vector(size, make_vector(sizes, x)); } } } // detail:: template auto make_vector(size_t const(&sizes)[Nb], Tp const& x = Tp()) { std::vector s(Nb); for (size_t i = 0; i < Nb; ++i) s[i] = sizes[Nb-i-1]; return detail::make_vector(s, x); } #line 1 "~/git/library/DataStructure/disjoint_set.cpp" /** * @brief 素集合データ構造 * @author えびちゃん */ #line 13 "~/git/library/DataStructure/disjoint_set.cpp" class disjoint_set { public: using size_type = size_t; private: mutable std::vector M_c; public: disjoint_set() = default; explicit disjoint_set(size_type n): M_c(n, -1) {} void reset() { M_c.assign(M_c.size(), -1); } size_type representative(size_type v) const { if (M_c[v] < 0) return v; return (M_c[v] = representative(M_c[v])); } bool unite(size_type u, size_type v) { u = representative(u); v = representative(v); if (u == v) return false; if (-M_c[u] > -M_c[v]) std::swap(u, v); M_c[v] += M_c[u]; M_c[u] = v; return true; } bool equivalent(size_type u, size_type v) const { return (representative(u) == representative(v)); } size_type size() const noexcept { return M_c.size(); } size_type count(size_type v) const { return -M_c[representative(v)]; } }; #line 1 "~/git/library/DataStructure/integral_intervals.cpp" /** * @brief 整数の区間の集合 * @author えびちゃん */ #line 10 "~/git/library/DataStructure/integral_intervals.cpp" #include #line 12 "~/git/library/DataStructure/integral_intervals.cpp" template class integral_intervals { public: using size_type = size_t; using value_type = Tp; using interval_type = std::pair; private: std::set M_intervals; size_type M_size = 0; public: integral_intervals() = default; integral_intervals(integral_intervals const&) = default; integral_intervals(integral_intervals&&) = default; integral_intervals& operator =(integral_intervals const&) = default; integral_intervals& operator =(integral_intervals&&) = default; template integral_intervals(InputIt first, InputIt last) { assign(first, last); } integral_intervals(std::initializer_list il) { assign(il.begin(), il.end()); } template void assign(InputIt first, InputIt last) { while (first != last) { insert(first->first, first->second); ++first; } } void insert(value_type x) { value_type y = x; insert(x, ++y); } void erase(value_type x) { value_type y = x; erase(x, ++y); } void insert(value_type lb, value_type ub) { if (lb >= ub) return; if (M_intervals.empty()) { M_size += ub - lb; M_intervals.emplace(lb, ub); return; } auto it = M_intervals.upper_bound({lb, lb}); if (it != M_intervals.begin() && !(std::prev(it)->second < lb)) { auto pit = std::prev(it); if (!(pit->second < ub)) return; lb = pit->first; M_size -= pit->second - pit->first; M_intervals.erase(pit); } while (it != M_intervals.end() && !(ub < it->first)) { if (ub < it->second) ub = it->second; M_size -= it->second - it->first; it = M_intervals.erase(it); } M_size += ub - lb; M_intervals.emplace(lb, ub); } void erase(value_type lb, value_type ub) { if (M_intervals.empty()) return; auto it = M_intervals.upper_bound({lb, lb}); if (it != M_intervals.begin() && !(std::prev(it)->second < lb)) { auto pit = std::prev(it); if (!(pit->second < ub)) { // [ ...* [ ...+ ) ...* ) --it; value_type lb0 = it->first; value_type ub0 = it->second; M_size -= it->second - it->first; M_intervals.erase(it); if (lb0 < lb) { M_size += lb - lb0; M_intervals.emplace(lb0, lb); } if (ub < ub0) { M_size += ub0 - ub; M_intervals.emplace(ub, ub0); } return; } // [ ...+ ) [ ...+ )* // [ ...+ ) <- erase this value_type lb0 = pit->first; M_size -= pit->second - pit->first; M_size += lb - lb0; M_intervals.erase(pit); M_intervals.emplace(lb0, lb); } while (it != M_intervals.end() && !(ub < it->first)) { if (ub < it->second) { value_type ub0 = it->second; M_size -= it->second - it->first; M_size += ub0 - ub; M_intervals.erase(it); M_intervals.emplace(ub, ub0); break; } M_size -= it->second - it->first; it = M_intervals.erase(it); } } interval_type range(value_type x) const { if (M_intervals.empty()) return {x, x}; auto it = M_intervals.upper_bound({x, x}); if (it != M_intervals.end()) if (!(x < it->first) && x < it->second) return *it; if (it == M_intervals.begin() || !(x < (--it)->second)) return {x, x}; return *it; } bool contains(value_type x) const { return (range(x).second != x); } value_type mex() const { return range(0).second; } bool empty() const noexcept { return (M_size == 0); } size_type size() const { return M_size; } size_type count() const { return M_intervals.size(); } auto begin() const { return M_intervals.begin(); } auto end() const { return M_intervals.end(); } }; #line 11 "C.cpp" int main() { size_t n; int64_t a, b; scan("{} {} {}", n, a, b); std::vector x(n); for (auto& xi: x) scan("{}", xi); integral_intervals seg; for (size_t i = 0; i < n; ++i) { auto il = std::lower_bound(x.begin(), x.end(), x[i]+a); auto ir = std::upper_bound(x.begin(), x.end(), x[i]+b); if (il == x.end()) continue; --ir; seg.insert(*il, *ir+1); } disjoint_set ds(n+n); { size_t j = 0; for (auto [s, e]: seg) { eprintln("seg [{}, {})", s, e); size_t il = std::lower_bound(x.begin(), x.end(), s-b) - x.begin(); size_t ir = std::lower_bound(x.begin(), x.end(), e-a) - x.begin(); eprintln("[{}, {}) to {}", il, ir, j+n); for (size_t i = il; i < ir; ++i) ds.unite(i, j+n); ++j; } } { std::map, size_t> ss; for (auto se: seg) ss[se]; size_t m = n; for (auto& [d, e]: ss) e = m++; for (size_t i = 0; i < n; ++i) { auto tmp = seg.range(x[i]); if (ss.count(tmp) == 0) continue; ds.unite(ss.at(tmp), i); } } std::vector res(n+n, 0); for (size_t i = 0; i < n+n; ++i) { if (ds.representative(i) == i) res[i] = ds.count(i); } for (size_t i = 0; i < n; ++i) { --res[ds.representative(n+i)]; } for (size_t i = 0; i < n; ++i) { println("{}", res[ds.representative(i)]); } }