#530500 (C++17) No.1170 Never Want to Walk

提出ソース
結果

問題	No.1170 Never Want to Walk
コンテスト
ユーザー	Pachicobue
提出日時	2020-08-14 22:23:01
言語	C++17 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	1,478 ms / 2,000 ms
コード長	11,985 bytes
コンパイル時間	3,947 ms
コンパイル使用メモリ	216,300 KB
最終ジャッジ日時	2025-01-13 00:08:41
ジャッジサーバーID （参考情報）	judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 2
other	AC * 37
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <bits/stdc++.h>

using ll                            = long long;
using uint                          = unsigned int;
using ull                           = unsigned long long;
using ld                            = long double;
template<typename T> using max_heap = std::priority_queue<T>;
template<typename T> using min_heap = std::priority_queue<T, std::vector<T>, std::greater<T>>;
constexpr int popcount(const ull v) { return v ? __builtin_popcountll(v) : 0; }
constexpr int log2p1(const ull v) { return v ? 64 - __builtin_clzll(v) : 0; }
constexpr int lsbp1(const ull v) { return __builtin_ffsll(v); }
constexpr int clog(const ull v) { return v ? log2p1(v - 1) : 0; }
constexpr ull ceil2(const ull v) { return 1ULL << clog(v); }
constexpr ull floor2(const ull v) { return v ? (1ULL << (log2p1(v) - 1)) : 0ULL; }
constexpr bool btest(const ull mask, const int ind) { return (mask >> ind) & 1ULL; }
template<typename T> void bset(T& mask, const int ind) { mask |= ((T)1 << ind); }
template<typename T> void breset(T& mask, const int ind) { mask &= ~((T)1 << ind); }
template<typename T> void bflip(T& mask, const int ind) { mask ^= ((T)1 << ind); }
template<typename T> void bset(T& mask, const int ind, const bool b) { (b ? bset(mask, ind) : breset(mask, ind)); }
template<typename T> bool chmin(T& a, const T& b) { return (a > b ? a = b, true : false); }
template<typename T> bool chmax(T& a, const T& b) { return (a < b ? a = b, true : false); }
template<typename T> constexpr T inf_v      = std::numeric_limits<T>::max() / 4;
template<typename Real> constexpr Real pi_v = Real{3.141592653589793238462643383279502884};
template<typename T> constexpr T TEN(const int n) { return n == 0 ? T{1} : TEN<T>(n - 1) * T{10}; }
template<typename F> struct fix : F
{
    fix(F&& f) : F{std::forward<F>(f)} {}
    template<typename... Args> auto operator()(Args&&... args) const { return F::operator()(*this, std::forward<Args>(args)...); }
};
template<typename T, int n, int i = 0>
auto nd_array(int const (&szs)[n], const T x = T{})
{
    if constexpr (i == n) {
        return x;
    } else {
        return std::vector(szs[i], nd_array<T, n, i + 1>(szs, x));
    }
}
class printer
{
public:
    printer(std::ostream& os_ = std::cout) : os{os_} { os << std::fixed << std::setprecision(15); }
    template<typename T> int operator()(const T& v) { return os << v, 0; }
    template<typename T> int operator()(const std::vector<T>& vs)
    {
        for (int i = 0; i < (int)vs.size(); i++) { os << (i ? " " : ""), this->operator()(vs[i]); }
        return 0;
    }
    template<typename T> int operator()(const std::vector<std::vector<T>>& vss)
    {
        for (int i = 0; i < (int)vss.size(); i++) { os << (0 <= i or i + 1 < (int)vss.size() ? "\n" : ""), this->operator()(vss[i]); }
        return 0;
    }
    template<typename T, typename... Args> int operator()(const T& v, const Args&... args) { return this->operator()(v), os << ' ', this->operator()(args...), 0; }
    template<typename... Args> int ln(const Args&... args) { return this->operator()(args...), os << '\n', 0; }
    template<typename... Args> int el(const Args&... args) { return this->operator()(args...), os << std::endl, 0; }
    template<typename... Args> int fmt(const std::string& s, const Args&... args) { return rec(s, 0, args...); }

private:
    int rec(const std::string& s, int index) { return os << s.substr(index, s.size()), 0; }
    template<typename T, typename... Args> int rec(const std::string& s, int index, const T& v, const Args&... args) { return index == s.size() ? 0 : s[index] == '%' ? (this->operator()(v), rec(s, index + 1, args...)) : (os << s[index], rec(s, index + 1, v, args...)); }
    std::ostream& os;
};
printer out;
class scanner
{
public:
    scanner(std::istream& is_ = std::cin) : is{is_} { is.tie(nullptr), std::ios::sync_with_stdio(false); }
    template<typename T> T val()
    {
        T v;
        return is >> v, v;
    }
    template<typename T> T val(const T offset) { return val<T>() - offset; }
    template<typename T> std::vector<T> vec(const int n)
    {
        std::vector<T> vs(n);
        for (auto& v : vs) { v = val<T>(); }
        return vs;
    }
    template<typename T> std::vector<T> vec(const int n, const T offset)
    {
        std::vector<T> vs(n);
        for (auto& v : vs) { v = val<T>(offset); }
        return vs;
    }
    template<typename T> std::vector<std::vector<T>> vvec(const int n0, const int n1)
    {
        std::vector<std::vector<T>> vss(n0);
        for (auto& vs : vss) { vs = vec<T>(n1); }
        return vss;
    }
    template<typename T> std::vector<std::vector<T>> vvec(const int n0, const int n1, const T offset)
    {
        std::vector<std::vector<T>> vss(n0);
        for (auto& vs : vss) { vs = vec<T>(n1, offset); }
        return vss;
    }
    template<typename... Args> auto tup() { return std::tuple<std::decay_t<Args>...>{val<Args>()...}; }
    template<typename... Args> auto tup(const Args&... offsets) { return std::tuple<std::decay_t<Args>...>{val<Args>(offsets)...}; }

private:
    std::istream& is;
};
scanner in;
#    define SHOW(...) static_cast<void>(0)

class segments
{
private:
    using pii = std::pair<int, int>;
    const int ceil;
    std::vector<pii> segs;
    const int num;

public:
    segments(const int size) : ceil{(int)ceil2(size)}, segs(ceil << 1, pii{0, 0}), num{ceil << 1}
    {
        for (int sz = 1; sz <= ceil; sz <<= 1) {
            const int len = ceil / sz;
            for (int j = sz; j < (sz << 1); j++) { segs[j] = {len * (j - sz), len * (j - sz + 1)}; }
        }
    }
    std::vector<int> under(int l, int r) const
    {
        if (l >= r or r > ceil) { return std::vector<int>{}; }
        std::vector<int> linds, rinds;
        for (l += ceil, r += ceil; l < r; l >>= 1, r >>= 1) {
            if (l & 1) { linds.push_back(l++); }
            if (r & 1) { rinds.push_back(--r); }
        }
        for (; not rinds.empty(); rinds.pop_back()) { linds.push_back(rinds.back()); }
        return linds;
    }
    std::vector<int> over(const int a) const
    {
        if (a >= ceil) { return std::vector<int>{}; }
        std::vector<int> aboves;
        for (int i = a + ceil; i >= 1; i >>= 1) { aboves.push_back(i); }
        std::reverse(aboves.begin(), aboves.end());
        return aboves;
    }
    const pii& operator[](const int i) const { return segs[i]; }
    int size() const { return num; }
};

template<typename T = int>
struct edge
{
    using cost_type = T;
    int v;
    T c;
    edge(const int v_) : v{v_}, c{1} {}
    edge(const int v_, const T& c_) : v{v_}, c{c_} {}
    operator int() const { return v; }
    int to() const { return v; }
    T cost() const { return c; }
    friend std::ostream& operator<<(std::ostream& os, const edge& e) { return os << e.u << "->" << e.v << ":" << e.c; }
};
template<typename Edge>
class base_graph
{
public:
    base_graph(const int n) : sz{n}, es(n), res(n)
    {}
    void add_edge(const int u, const int v, const bool bi = false)
    {
        es[u].emplace_back(v);
        res[v].emplace_back(u);
        if (bi) {
            es[v].emplace_back(u);
            res[u].emplace_back(v);
        }
    }
    template<typename Cost>
    void add_edge(const int u, const int v, const Cost& c, const bool bi = false)
    {
        es[u].emplace_back(v, c);
        res[v].emplace_back(u, c);
        if (bi) {
            es[v].emplace_back(u, c);
            res[u].emplace_back(v, c);
        }
    }
    std::vector<Edge>& operator[](const int u) { return es[u]; }
    const std::vector<Edge>& operator[](const int u) const { return es[u]; }
    std::vector<Edge>& from(const int u) { return es[u]; }
    const std::vector<Edge>& from(const int u) const { return es[u]; }
    std::vector<Edge>& to(const int v) { return res[v]; }
    const std::vector<Edge>& to(const int v) const { return res[v]; }
    int size() const { return sz; }
    friend std::ostream& operator<<(std::ostream& os, const base_graph& g)
    {
        for (int i = 0; i < g.sz; i++) {
            for (const auto& e : g.es[i]) { os << e << '\n'; }
        }
        return os;
    }

private:
    int sz;
    std::vector<std::vector<Edge>> es, res;
};
using graph = base_graph<edge<>>;
template<typename Cost>
using cost_graph = base_graph<edge<Cost>>;
template<typename Edge = edge<>>
class sc_comp
{
public:
    sc_comp(const base_graph<Edge>& g) : sz(g.size()), cmp(sz, sz)
    {
        std::vector<int> st;
        std::vector<bool> used(sz, false);
        auto dfs1 = [&](auto&& self, const int s) -> void {
            used[s] = true;
            for (const auto& e : g[s]) {
                const int to = e.to();
                if (not used[to]) { self(self, to); }
            }
            st.push_back(s);
        };
        auto dfs2 = [&](auto&& self, const int s) -> void {
            cmp[s] = cnum;
            for (const auto& e : g.to(s)) {
                const int to = e.to();
                if (cmp[to] != sz) { continue; }
                self(self, to);
            }
        };
        for (int i = 0; i < sz; i++) {
            if (used[i]) { continue; }
            dfs1(dfs1, i);
        }
        for (int i = 0; i < (int)st.size(); i++) {
            const int s = st[st.size() - i - 1];
            if (cmp[s] != sz) { continue; }
            dfs2(dfs2, s), cnum++;
        }
    }
    int operator[](const int v) const { return cmp[v]; }
    int comp_num() const { return cnum; }

private:
    int sz, cnum = 0;
    std::vector<int> cmp;
};

template<typename Edge>
std::pair<bool, std::vector<int>> top_sort(const base_graph<Edge>& g)
{
    const int v = g.size();
    std::vector<int> srt, used(v, 0);
    auto dfs = [&](auto&& self, const int s) -> bool {
        if (used[s] == 1) {
            return false;
        } else if (used[s] == 0) {
            used[s] = 1;
            for (const auto& e : g[s]) {
                const int to = e.to();
                if (not self(self, to)) { return false; }
            }
            used[s] = 2, srt.push_back(s);
        }
        return true;
    };
    for (int i = 0; i < v; i++) {
        if (not dfs(dfs, i)) { return {false, srt}; }
    }
    std::reverse(srt.begin(), srt.end());
    return {true, srt};
}
int main()
{
    const auto N      = in.val<int>();
    const auto [A, B] = in.tup<ll, ll>();
    const auto xs     = in.vec<ll>(N);
    auto segs         = segments(N);
    const int n       = segs.size();
    const int h       = n / 2;
    graph g(n);
    for (int i = 1; i < n; i++) {
        if (2 * i < n) { g.add_edge(i, i * 2); }
        if (2 * i + 1 < n) { g.add_edge(i, i * 2 + 1); }
    }
    for (int i = 0; i < N; i++) {
        const int mini1 = std::lower_bound(xs.begin(), xs.end(), xs[i] - B) - xs.begin();
        const int supi1 = std::upper_bound(xs.begin(), xs.end(), xs[i] - A) - xs.begin();
        if (supi1 - mini1 >= 1) {
            const auto inds = segs.under(mini1, supi1);
            for (const int ind : inds) { g.add_edge(i + h, ind); }
        }
        const int mini2 = std::lower_bound(xs.begin(), xs.end(), xs[i] + A) - xs.begin();
        const int supi2 = std::upper_bound(xs.begin(), xs.end(), xs[i] + B) - xs.begin();
        if (supi2 - mini2 >= 1) {
            const auto inds = segs.under(mini2, supi2);
            for (const int ind : inds) { g.add_edge(i + h, ind); }
        }
    }
    const sc_comp scc{g};
    const int m = scc.comp_num();
    std::vector<int> cn(m, 0);
    for (int i = 0; i < N; i++) { cn[scc[i + h]]++; }
    graph dag(m);
    for (int i = 0; i < n; i++) {
        for (const int to : g[i]) {
            if (scc[i] != scc[to]) { dag.add_edge(scc[to], scc[i]); }
        }
    }
    const auto is = top_sort(dag).second;
    std::vector<int> dp(m, 0);
    for (const int i : is) {
        dp[i] += cn[i];
        for (const int to : dag[i]) { dp[to] += dp[i]; }
    }
    for (int i = 0; i < N; i++) { out.ln(dp[scc[i + h]]); }

    return 0;
}
yukicoder

結果

ソースコード
