#906538 (C++23) No.2242 Cities and Teleporters

提出ソース
結果

問題	No.2242 Cities and Teleporters
コンテスト
ユーザー	Pachicobue
提出日時	2023-08-20 23:35:40
言語	C++23 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	569 ms / 3,000 ms
コード長	15,358 bytes
コンパイル時間	4,059 ms
コンパイル使用メモリ	276,864 KB
実行使用メモリ	41,748 KB
最終ジャッジ日時	2024-12-14 06:30:14
合計ジャッジ時間	16,415 ms
ジャッジサーバーID （参考情報）	judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
other	AC * 26
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <bits/stdc++.h>
using i32 = int;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128_t;
using u128 = __uint128_t;
using f64 = double;
using f80 = long double;
using f128 = __float128;
constexpr i32 operator"" _i32(u64 v) { return v; }
constexpr u32 operator"" _u32(u64 v) { return v; }
constexpr i64 operator"" _i64(u64 v) { return v; }
constexpr u64 operator"" _u64(u64 v) { return v; }
constexpr f64 operator"" _f64(f80 v) { return v; }
constexpr f80 operator"" _f80(f80 v) { return v; }
using Istream = std::istream;
using Ostream = std::ostream;
using Str = std::string;
template<typename T> using Lt = std::less<T>;
template<typename T> using Gt = std::greater<T>;
template<int n> using BSet = std::bitset<n>;
template<typename T1, typename T2> using Pair = std::pair<T1, T2>;
template<typename... Ts> using Tup = std::tuple<Ts...>;
template<typename T, int N> using Arr = std::array<T, N>;
template<typename... Ts> using Deq = std::deque<Ts...>;
template<typename... Ts> using Set = std::set<Ts...>;
template<typename... Ts> using MSet = std::multiset<Ts...>;
template<typename... Ts> using USet = std::unordered_set<Ts...>;
template<typename... Ts> using UMSet = std::unordered_multiset<Ts...>;
template<typename... Ts> using Map = std::map<Ts...>;
template<typename... Ts> using MMap = std::multimap<Ts...>;
template<typename... Ts> using UMap = std::unordered_map<Ts...>;
template<typename... Ts> using UMMap = std::unordered_multimap<Ts...>;
template<typename... Ts> using Vec = std::vector<Ts...>;
template<typename... Ts> using Stack = std::stack<Ts...>;
template<typename... Ts> using Queue = std::queue<Ts...>;
template<typename T> using MaxHeap = std::priority_queue<T>;
template<typename T> using MinHeap = std::priority_queue<T, Vec<T>, Gt<T>>;
template<typename T> using Opt = std::optional<T>;
template<typename... Ts> using Span = std::span<Ts...>;
constexpr bool LOCAL = false;
template<typename T> static constexpr T OjLocal(T oj, T local) { return LOCAL ? local : oj; }
template<typename T> constexpr T LIMMIN = std::numeric_limits<T>::min();
template<typename T> constexpr T LIMMAX = std::numeric_limits<T>::max();
template<typename T> constexpr T INF = (LIMMAX<T> - 1) / 2;
template<typename T = i64> constexpr T TEN(int N) { return N == 0 ? T{1} : TEN<T>(N - 1) * T{10}; }
constexpr auto ABS(auto x) { return (x >= 0 ? x : -x); }
constexpr auto makePair(const auto& x1, const auto& x2) { return std::make_pair(x1, x2); }
constexpr auto makeTup(const auto&... xs) { return std::make_tuple(xs...); }
template<typename T> constexpr bool chmin(T& x, const T& y, auto comp) { return (comp(y, x) ? (x = y, true) : false); }
template<typename T> constexpr bool chmin(T& x, const T& y) { return chmin(x, y, Lt<T>{}); }
template<typename T> constexpr bool chmax(T& x, const T& y, auto comp) { return (comp(x, y) ? (x = y, true) : false); }
template<typename T> constexpr bool chmax(T& x, const T& y) { return chmax(x, y, Lt<T>{}); }
constexpr i64 floorDiv(i64 x, i64 y)
{
    assert(y != 0);
    if (y < 0) { x = -x, y = -y; }
    return x >= 0 ? x / y : (x - y + 1) / y;
}
constexpr i64 ceilDiv(i64 x, i64 y)
{
    assert(y != 0);
    if (y < 0) { x = -x, y = -y; }
    return x >= 0 ? (x + y - 1) / y : x / y;
}
template<typename T> constexpr T powerSemiGroup(const T& x, i64 N, auto mul)
{
    assert(N > 0);
    if (N == 1) { return x; }
    return (N % 2 == 1 ? mul(x, powerSemiGroup(x, N - 1, mul)) : powerSemiGroup(mul(x, x), N / 2, mul));
}
template<typename T> constexpr T powerSemiGroup(const T& x, i64 N) { return powerSemiGroup(x, N, std::multiplies<T>{}); }
template<typename T> constexpr T powerMonoid(const T& x, i64 N, const T& e, auto mul)
{
    assert(N >= 0);
    return (N == 0 ? e : powerSemiGroup(x, N, mul));
}
template<typename T> constexpr T powerMonoid(const T& x, i64 N, const T& e) { return powerMonoid(x, N, e, std::multiplies<T>{}); }
template<typename T> constexpr T powerInt(const T& x, i64 N) { return powerMonoid(x, N, T{1}); }
constexpr u64 powerMod(u64 x, i64 N, u64 mod)
{
    assert(0 < mod);
    return powerMonoid(x, N, u64{1}, [&](u64 x, u64 y) {
        if (mod <= (u64)LIMMAX<u32>) {
            return x * y % mod;
        } else {
            return (u64)((u128)x * y % mod);
        }
    });
}
void seqConcat(auto& xs1, const auto& xs2) { std::ranges::copy(xs2, std::back_inserter(xs1)); }
auto seqConcatCopy(const auto& xs1, const auto& xs2)
{
    auto Ans = xs1;
    return seqConcat(Ans, xs2), Ans;
}
int seqMinInd(const auto& xs, auto... args) { return std::ranges::min_element(xs, args...) - std::begin(xs); }
int seqMaxInd(const auto& xs, auto... args) { return std::ranges::max_element(xs, args...) - std::begin(xs); }
void seqReverse(auto& xs) { std::ranges::reverse(xs); }
void seqSort(auto& xs, auto... args) { std::ranges::sort(xs, args...); }
template<typename T> Vec<T> genVec(int N, auto gen)
{
    Vec<T> ans;
    std::ranges::generate_n(std::back_inserter(ans), N, gen);
    return ans;
}
template<typename T = int> Vec<T> iotaVec(int N, T offset = 0)
{
    Vec<T> ans(N);
    std::iota(std::begin(ans), std::end(ans), offset);
    return ans;
}
auto seqRleVec(const auto& xs)
{
    using T = std::remove_cvref_t<decltype(xs[0])>;
    Vec<Pair<T, int>> Ans;
    auto [l, px] = makePair(0, T{});
    for (const T& x : xs) {
        if (l == 0 or x != px) {
            if (l > 0) { Ans.push_back({px, l}); }
            l = 1, px = x;
        } else {
            l++;
        }
    }
    if (l > 0) { Ans.push_back({px, l}); }
    return Ans;
}
int sortedLbInd(const auto& xs, const auto& x, auto... args) { return std::ranges::lower_bound(xs, x, args...) - std::begin(xs); }
int sortedUbInd(const auto& xs, const auto& x, auto... args) { return std::ranges::upper_bound(xs, x, args...) - std::begin(xs); }
int sortedFind(const auto& xs, const auto& x, auto... args)
{
    const int i = sortedLbInd(xs, x, args...);
    if (i < std::ssize(xs) and xs[i] == x) { return i; }
    return std::ssize(xs);
}
void mdSeqAct(auto& xs, auto f)
{
    if constexpr (requires(const decltype(xs) xs) { std::begin(xs); }) {
        for (auto& x : xs) { mdSeqAct(x, f); }
    } else {
        f(xs);
    }
}
[[nodiscard]] auto mdSeqFold(const auto& xs, auto op)
{
    if constexpr (requires(const decltype(xs) xs) { std::begin(xs); }) {
        assert(std::size(xs) > 0);
        auto ans = mdSeqFold(xs[0], op);
        for (int i = 1; i < std::ssize(xs); i++) { ans = op(ans, mdSeqFold(xs[i], op)); }
        return ans;
    } else {
        return xs;
    }
}
void mdSeqFill(auto& xs, auto x)
{
    mdSeqAct(xs, [&x](auto& v) { v = x; });
}
void mdSeqPlus(auto& xs, auto x)
{
    mdSeqAct(xs, [&x](auto& v) { v += x; });
}
auto mdSeqSum(const auto& xs)
{
    return mdSeqFold(xs, [](auto x, auto y) { return x + y; });
}
auto mdSeqMin(const auto& xs, auto... args)
{
    return mdSeqFold(xs, [&args...](auto x, auto y) { return std::ranges::min(x, y, args...); });
}
auto mdSeqMax(const auto& xs, auto... args)
{
    return mdSeqFold(xs, [&args...](auto x, auto y) { return std::ranges::max(x, y, args...); });
}
inline Ostream& operator<<(Ostream& os, u128 v)
{
    Str ans;
    if (v == 0) { ans = "0"; }
    while (v) { ans.push_back('0' + v % 10), v /= 10; }
    std::reverse(ans.begin(), ans.end());
    return os << ans;
}
inline Ostream& operator<<(Ostream& os, i128 v)
{
    bool minus = false;
    if (v < 0) { minus = true, v = -v; }
    return os << (minus ? "-" : "") << (u128)v;
}
constexpr bool isBitOn(u64 x, int i) { return assert(0 <= i and i < 64), ((x >> i) & 1_u64); }
constexpr bool isBitOff(u64 x, int i) { return assert(0 <= i and i < 64), (not isBitOn(x, i)); }
constexpr u64 bitMask(int w) { return assert(0 <= w and w <= 64), (w == 64 ? ~0_u64 : (1_u64 << w) - 1); }
constexpr u64 bitMask(int s, int e) { return assert(0 <= s and s <= e and e <= 64), (bitMask(e - s) << s); }
constexpr int floorLog2(u64 x) { return 63 - std::countl_zero(x); }
constexpr int ceilLog2(u64 x) { return x == 0 ? -1 : std::bit_width(x - 1); }
constexpr int order2(u64 x) { return std::countr_zero(x); }
template<typename F> struct Fix : F
{
    constexpr Fix(F&& f) : F{std::forward<F>(f)} {}
    template<typename... Args> constexpr auto operator()(Args&&... args) const
    {
        return F::operator()(*this, std::forward<Args>(args)...);
    }
};
class irange
{
private:
    struct itr
    {
        constexpr itr(i64 start, i64 end, i64 step) : m_cnt{start}, m_step{step}, m_end{end} {}
        constexpr bool operator!=(const itr&) const { return (m_step > 0 ? m_cnt < m_end : m_end < m_cnt); }
        constexpr i64 operator*() { return m_cnt; }
        constexpr itr& operator++() { return m_cnt += m_step, *this; }
        i64 m_cnt, m_step, m_end;
    };
    i64 m_start, m_end, m_step;
public:
    constexpr irange(i64 start, i64 end, i64 step = 1) : m_start{start}, m_end{end}, m_step{step} { assert(step != 0); }
    constexpr itr begin() const { return itr{m_start, m_end, m_step}; }
    constexpr itr end() const { return itr{m_start, m_end, m_step}; }
};
constexpr irange rep(i64 end) { return irange(0, end, 1); }
constexpr irange per(i64 rend) { return irange(rend - 1, -1, -1); }
template<typename Monoid> class Doubling
{
    using T = typename Monoid::T;
public:
    Doubling(Vec<int> f, const Vec<T>& w) : m_N{(int)f.size()}
    {
        assert(f.size() == w.size());
        assert(std::ranges::all_of(f, [&](int x) { return -1 <= x and x <= m_N; }));
        Vec<int> nexts{0};
        mdSeqPlus(f, 1), seqConcat(nexts, f), nexts.push_back(m_N + 1);
        Vec<T> ws{Monoid::e()};
        seqConcat(ws, w), ws.push_back(Monoid::e());
        m_nextss.push_back(nexts), m_wss.push_back(ws);
    }
    Pair<int, T> kthNext(int x, i64 K)
    {
        assert(0 <= x and x < m_N);
        assert(K >= 0);
        x++;
        resize(K);
        T D = Monoid::e();
        for (int d : rep(m_nextss.size())) {
            if (isBitOn(K, d)) { D = merge(D, m_wss[d][x]), x = m_nextss[d][x]; }
        }
        return {x - 1, D};
    }
    i64 distance(int x, const i64 Kmax, auto pred)
    {
        assert(0 <= x and x < m_N);
        assert(0 <= Kmax);
        x++;
        resize(Kmax);
        T D = Monoid::e();
        if (pred(x - 1, D)) { return 0; }
        const int lg = (int)m_nextss.size();
        i64 ans = 0;
        for (int d : per(lg)) {
            const int np = m_nextss[d][x];
            const T nD = merge(D, m_wss[d][x]);
            if (ans + (1_i64 << d) <= Kmax and not pred(np - 1, nD)) {
                x = np, D = nD;
                ans += (1_i64 << d);
            }
        }
        return ans + 1;
    }
private:
    void resize(i64 KMax)
    {
        if (KMax <= 1) { return; }
        const int L = ceilLog2(KMax) + 1;
        while (std::ssize(m_nextss) < L) {
            const auto& pnexts = m_nextss.back();
            const auto& pws = m_wss.back();
            Vec<int> nnexts(m_N + 2);
            Vec<T> nws(m_N + 2);
            for (int i : rep(m_N + 2)) { nnexts[i] = pnexts[pnexts[i]], nws[i] = merge(pws[i], pws[pnexts[i]]); }
            m_nextss.push_back(nnexts), m_wss.push_back(nws);
        }
    }
    int m_N;
    Vec<Vec<int>> m_nextss;
    Vec<Vec<T>> m_wss;
    static inline Monoid merge;
};
class Printer
{
public:
    Printer(Ostream& os = std::cout) : m_os{os} { m_os << std::fixed << std::setprecision(15); }
    int operator()(const auto&... args) { return dump(args...), 0; }
    int ln(const auto&... args) { return dump(args...), m_os << '\n', 0; }
    int el(const auto&... args) { return dump(args...), m_os << std::endl, 0; }
private:
    void dump(const auto& v) { m_os << v; }
    int dump(const auto& v, const auto&... args) { return dump(v), m_os << ' ', dump(args...), 0; }
    template<typename... Args> void dump(const Vec<Args...>& vs)
    {
        for (Str delim = ""; const auto& v : vs) { m_os << std::exchange(delim, " "), dump(v); }
    }
    Ostream& m_os;
};
inline Printer out;
class Scanner
{
public:
    Scanner(Istream& is = std::cin) : m_is{is} { m_is.tie(nullptr)->sync_with_stdio(false); }
    template<typename T> T val()
    {
        T v;
        return m_is >> v, v;
    }
    template<typename T> T val(T offset) { return val<T>() - offset; }
    template<typename T> Vec<T> vec(int N)
    {
        return genVec<T>(N, [&]() { return val<T>(); });
    }
    template<typename T> Vec<T> vec(int N, T offset)
    {
        return genVec<T>(N, [&]() { return val<T>(offset); });
    }
    template<typename T> Vec<Vec<T>> vvec(int n, int m)
    {
        return genVec<Vec<T>>(n, [&]() { return vec<T>(m); });
    }
    template<typename T> Vec<Vec<T>> vvec(int n, int m, const T offset)
    {
        return genVec<Vec<T>>(n, [&]() { return vec<T>(m, offset); });
    }
    template<typename... Args> auto tup() { return Tup<Args...>{val<Args>()...}; }
    template<typename... Args> auto tup(Args... offsets) { return Tup<Args...>{val<Args>(offsets)...}; }
private:
    Istream& m_is;
};
inline Scanner in;
template<typename T> class Zipper
{
public:
    Zipper() {}
    Zipper(const Vec<T>& Xs) : m_vs{Xs}, m_calced(false) {}
    T unzip(int x)
    {
        calc();
        assert(0 <= x and x < size());
        return m_vs[x];
    }
    int zip(T X)
    {
        calc();
        assert(sortedFind(m_vs, X) < (int)m_vs.size());
        return sortedLbInd(m_vs, X);
    }
    void add(T X) { m_vs.push_back(X), m_calced = false; }
    void add(const Vec<T>& Xs)
    {
        for (const auto& v : Xs) { m_vs.push_back(v); }
        m_calced = false;
    }
    int size()
    {
        calc();
        return m_vs.size();
    }
private:
    void calc()
    {
        if (not m_calced) {
            seqSort(m_vs);
            m_vs.erase(std::unique(m_vs.begin(), m_vs.end()), m_vs.end());
            m_calced = true;
        }
    }
    Vec<T> m_vs;
    bool m_calced = true;
};
struct Monoid
{
    using T = int;
    static constexpr T e()
    {
        return -INF<int>;
    }
    T operator()(const T& x1, const T& x2) const
    {
        return std::max(x1, x2);
    }
};
int main()
{
    const auto N = in.val<int>();
    const auto Hs = in.vec<int>(N);
    const auto Ts = in.vec<int>(N);
    auto is = iotaVec(N), ris = Vec<int>(N);
    seqSort(is, [&](int i, int j) {
        return Hs[i] < Hs[j];
    });
    for (int i : rep(N)) {
        ris[is[i]] = i;
    }
    Vec<int> hs(N), ts(N);
    for (int i : rep(N)) {
        hs[i] = Hs[is[i]], ts[i] = Ts[is[i]];
    }
    auto mts = ts;
    auto mtis = iotaVec(N);
    for (int i : rep(N - 1)) {
        if (chmax(mts[i + 1], mts[i])) {
            mtis[i + 1] = mtis[i];
        }
    }
    Vec<int> ns(N);
    for (int i : rep(N)) {
        const int ri = sortedUbInd(hs, ts[i]);
        ns[i] = (ri == 0 ? -1 : mtis[ri - 1]);
    }
    Doubling<Monoid> doubling(ns, ts);
    const auto Q = in.val<int>();
    for (auto _temp_name_0 [[maybe_unused]] : rep(Q)) {
        const auto [A, B] = in.tup<int, int>(1, 1);
        if (A == B) {
            out.ln(0);
        } else {
            const int a = ris[A], b = ris[B];
            int d = doubling.distance(a, N, [&](int, int d) {
                return hs[b] <= d;
            });
            chmax(d, 1);
            out.ln(d == N + 1 ? -1 : d);
        }
    }
    return 0;
}
yukicoder

結果

ソースコード
