#896196 (C++17) No.2395 区間二次変換一点取得

提出ソース
結果

問題	No.2395 区間二次変換一点取得
ユーザー	kobaryo222
提出日時	2023-07-28 22:09:46
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	266 ms / 2,000 ms
コード長	12,137 bytes
コンパイル時間	2,366 ms
コンパイル使用メモリ	209,244 KB
実行使用メモリ	8,576 KB
最終ジャッジ日時	2024-10-06 19:04:41
合計ジャッジ時間	5,991 ms
ジャッジサーバーID （参考情報）	judge5 / judge2
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,816 KB
testcase_02	AC	2 ms 6,816 KB
testcase_03	AC	2 ms 6,816 KB
testcase_04	AC	2 ms 6,820 KB
testcase_05	AC	2 ms 6,816 KB
testcase_06	AC	2 ms 6,820 KB
testcase_07	AC	2 ms 6,816 KB
testcase_08	AC	2 ms 6,820 KB
testcase_09	AC	2 ms 6,820 KB
testcase_10	AC	2 ms 6,820 KB
testcase_11	AC	4 ms 6,816 KB
testcase_12	AC	25 ms 6,820 KB
testcase_13	AC	258 ms 8,448 KB
testcase_14	AC	258 ms 8,576 KB
testcase_15	AC	258 ms 8,448 KB
testcase_16	AC	266 ms 8,448 KB
testcase_17	AC	251 ms 8,576 KB
testcase_18	AC	204 ms 8,576 KB
testcase_19	AC	199 ms 8,576 KB
権限があれば一括ダウンロードができます
ソースコード

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

using namespace std;

using ll = long long;
using pl = pair<ll, ll>;
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vvvl vector<vector<vector<ll>>>
#define vm vector<mint>
#define vvm vector<vector<mint>>
#define vvvm vector<vector<vector<mint>>>
#define vp vector<pl>
#define vvp vector<vector<pl>>
#define vs vector<string>
#define vvs vector<vector<string>>
#define vb vector<bool>
#define vvb vector<vb>
#define vvvb vector<vvb>

#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for(ll i = ll(a); i < ll(b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define all(x) std::begin(x), std::end(x)
#define make_unique(v) v.erase(unique(all(v)), v.end());
#define sum(...) accumulate(all(__VA_ARGS__), 0LL)
#define inf (0x1fffffffffffffffLL)

template <class T>
istream &operator>>(istream &is, vector<T> &v) {
    for(auto &x : v) {
        is >> x;
    }
    return is;
}

template <class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
    for(int i = 0; i < (int)v.size(); i++) {
        if(i != (int)v.size() - 1)
            os << v[i] << " ";
        else
            os << v[i];
    }
    return os;
}

template <typename T, typename... Args>
auto make_v(T x, int arg, Args... args) {
    if constexpr(sizeof...(args) == 0)
        return vector<T>(arg, x);
    else
        return vector(arg, make_v<T>(x, args...));
}

template <class T>
auto min(const T &a) {
    return *min_element(all(a));
}

template <class T>
auto max(const T &a) {
    return *max_element(all(a));
}

template <class T>
bool chmin(T &a, const T &b) {
    return a > b ? a = b, true : false;
}

template <class T>
bool chmax(T &a, const T &b) {
    return a < b ? a = b, true : false;
}

struct IoSetup {
    IoSetup() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(10);
        cerr << fixed << setprecision(10);
    }
} iosetup;
#line 2 "modint/arbitrary-modint.hpp"

#line 2 "modint/barrett-reduction.hpp"

#include <utility>
using namespace std;

struct Barrett {
    using u32 = unsigned int;
    using i64 = long long;
    using u64 = unsigned long long;
    u32 m;
    u64 im;
    Barrett()
      : m(), im() {}
    Barrett(int n)
      : m(n), im(u64(-1) / m + 1) {}
    constexpr inline i64 quo(u64 n) {
        u64 x = u64((__uint128_t(n) * im) >> 64);
        u32 r = n - x * m;
        return m <= r ? x - 1 : x;
    }
    constexpr inline i64 rem(u64 n) {
        u64 x = u64((__uint128_t(n) * im) >> 64);
        u32 r = n - x * m;
        return m <= r ? r + m : r;
    }
    constexpr inline pair<i64, int> quorem(u64 n) {
        u64 x = u64((__uint128_t(n) * im) >> 64);
        u32 r = n - x * m;
        if(m <= r) return {x - 1, r + m};
        return {x, r};
    }
    constexpr inline i64 pow(u64 n, i64 p) {
        u32 a = rem(n), r = m == 1 ? 0 : 1;
        while(p) {
            if(p & 1) r = rem(u64(r) * a);
            a = rem(u64(a) * a);
            p >>= 1;
        }
        return r;
    }
};
#line 4 "modint/arbitrary-modint.hpp"

template <int id>
struct ArbitraryModIntBase {
    int x;

    ArbitraryModIntBase()
      : x(0) {}

    ArbitraryModIntBase(int64_t y) {
        int z = y % get_mod();
        if(z < 0) z += get_mod();
        x = z;
    }

    ArbitraryModIntBase &operator+=(const ArbitraryModIntBase &p) {
        if((x += p.x) >= get_mod()) x -= get_mod();
        return *this;
    }

    ArbitraryModIntBase &operator-=(const ArbitraryModIntBase &p) {
        if((x += get_mod() - p.x) >= get_mod()) x -= get_mod();
        return *this;
    }

    ArbitraryModIntBase &operator*=(const ArbitraryModIntBase &p) {
        x = rem((unsigned long long)x * p.x);
        return *this;
    }

    ArbitraryModIntBase &operator/=(const ArbitraryModIntBase &p) {
        *this *= p.inverse();
        return *this;
    }

    ArbitraryModIntBase operator-() const { return ArbitraryModIntBase(-x); }
    ArbitraryModIntBase operator+() const { return *this; }

    ArbitraryModIntBase operator+(const ArbitraryModIntBase &p) const {
        return ArbitraryModIntBase(*this) += p;
    }

    ArbitraryModIntBase operator-(const ArbitraryModIntBase &p) const {
        return ArbitraryModIntBase(*this) -= p;
    }

    ArbitraryModIntBase operator*(const ArbitraryModIntBase &p) const {
        return ArbitraryModIntBase(*this) *= p;
    }

    ArbitraryModIntBase operator/(const ArbitraryModIntBase &p) const {
        return ArbitraryModIntBase(*this) /= p;
    }

    bool operator==(const ArbitraryModIntBase &p) const { return x == p.x; }

    bool operator!=(const ArbitraryModIntBase &p) const { return x != p.x; }

    ArbitraryModIntBase inverse() const {
        int a = x, b = get_mod(), u = 1, v = 0, t;
        while(b > 0) {
            t = a / b;
            swap(a -= t * b, b);
            swap(u -= t * v, v);
        }
        return ArbitraryModIntBase(u);
    }

    ArbitraryModIntBase pow(int64_t n) const {
        ArbitraryModIntBase ret(1), mul(x);
        while(n > 0) {
            if(n & 1) ret *= mul;
            mul *= mul;
            n >>= 1;
        }
        return ret;
    }

    friend ostream &operator<<(ostream &os, const ArbitraryModIntBase &p) {
        return os << p.x;
    }

    friend istream &operator>>(istream &is, ArbitraryModIntBase &a) {
        int64_t t;
        is >> t;
        a = ArbitraryModIntBase(t);
        return (is);
    }

    int get() const { return x; }

    inline unsigned int rem(unsigned long long p) { return barrett().rem(p); }

    static inline Barrett &barrett() {
        static Barrett b;
        return b;
    }

    static inline int &get_mod() {
        static int mod = 0;
        return mod;
    }

    static void set_mod(int md) {
        assert(0 < md && md <= (1LL << 30) - 1);
        get_mod() = md;
        barrett() = Barrett(md);
    }
};

using ArbitraryModInt = ArbitraryModIntBase<-1>;

/**
 * @brief Lazy-Segment-Tree(遅延伝搬セグメント木)
 * @docs docs/lazy-segment-tree.md
 */
template <typename T, typename E, typename F, typename G, typename H>
struct LazySegmentTree {
  private:
    int n{}, sz{}, height{};
    vector<T> data;
    vector<E> lazy;
    const F f;
    const G g;
    const H h;
    const T ti;
    const E ei;

    inline void update(int k) {
        data[k] = f(data[2 * k + 0], data[2 * k + 1]);
    }

    inline void all_apply(int k, const E &x) {
        data[k] = g(data[k], x);
        if(k < sz) lazy[k] = h(lazy[k], x);
    }

    inline void propagate(int k) {
        if(lazy[k] != ei) {
            all_apply(2 * k + 0, lazy[k]);
            all_apply(2 * k + 1, lazy[k]);
            lazy[k] = ei;
        }
    }

  public:
    LazySegmentTree() = default;

    explicit LazySegmentTree(int n, const F f, const G g, const H h,
                             const T &ti, const E &ei)
      : n(n), f(f), g(g), h(h), ti(ti), ei(ei) {
        sz = 1;
        height = 0;
        while(sz < n)
            sz <<= 1, height++;
        data.assign(2 * sz, ti);
        lazy.assign(2 * sz, ei);
    }

    explicit LazySegmentTree(const vector<T> &v, const F f, const G g, const H h,
                             const T &ti, const E &ei)
      : LazySegmentTree(v.size(), f, g, h, ti, ei) {
        build(v);
    }

    void build(const vector<T> &v) {
        assert(n == (int)v.size());
        for(int k = 0; k < n; k++)
            data[k + sz] = v[k];
        for(int k = sz - 1; k > 0; k--)
            update(k);
    }

    void set(int k, const T &x) {
        k += sz;
        for(int i = height; i > 0; i--)
            propagate(k >> i);
        data[k] = x;
        for(int i = 1; i <= height; i++)
            update(k >> i);
    }

    T get(int k) {
        k += sz;
        for(int i = height; i > 0; i--)
            propagate(k >> i);
        return data[k];
    }

    T operator[](int k) {
        return get(k);
    }

    T prod(int l, int r) {
        if(l >= r) return ti;
        l += sz;
        r += sz;
        for(int i = height; i > 0; i--) {
            if(((l >> i) << i) != l) propagate(l >> i);
            if(((r >> i) << i) != r) propagate((r - 1) >> i);
        }
        T L = ti, R = ti;
        for(; l < r; l >>= 1, r >>= 1) {
            if(l & 1) L = f(L, data[l++]);
            if(r & 1) R = f(data[--r], R);
        }
        return f(L, R);
    }

    T all_prod() const {
        return data[1];
    }

    void apply(int k, const E &x) {
        k += sz;
        for(int i = height; i > 0; i--)
            propagate(k >> i);
        data[k] = g(data[k], x);
        for(int i = 1; i <= height; i++)
            update(k >> i);
    }

    void apply(int l, int r, const E &x) {
        if(l >= r) return;
        l += sz;
        r += sz;
        for(int i = height; i > 0; i--) {
            if(((l >> i) << i) != l) propagate(l >> i);
            if(((r >> i) << i) != r) propagate((r - 1) >> i);
        }
        {
            int l2 = l, r2 = r;
            for(; l < r; l >>= 1, r >>= 1) {
                if(l & 1) all_apply(l++, x);
                if(r & 1) all_apply(--r, x);
            }
            l = l2, r = r2;
        }
        for(int i = 1; i <= height; i++) {
            if(((l >> i) << i) != l) update(l >> i);
            if(((r >> i) << i) != r) update((r - 1) >> i);
        }
    }

    template <typename C>
    int find_first(int l, const C &check) {
        if(l >= n) return n;
        l += sz;
        for(int i = height; i > 0; i--)
            propagate(l >> i);
        T sum = ti;
        do {
            while((l & 1) == 0)
                l >>= 1;
            if(check(f(sum, data[l]))) {
                while(l < sz) {
                    propagate(l);
                    l <<= 1;
                    auto nxt = f(sum, data[l]);
                    if(not check(nxt)) {
                        sum = nxt;
                        l++;
                    }
                }
                return l + 1 - sz;
            }
            sum = f(sum, data[l++]);
        } while((l & -l) != l);
        return n;
    }

    template <typename C>
    int find_last(int r, const C &check) {
        if(r <= 0) return -1;
        r += sz;
        for(int i = height; i > 0; i--)
            propagate((r - 1) >> i);
        T sum = ti;
        do {
            r--;
            while(r > 1 and (r & 1))
                r >>= 1;
            if(check(f(data[r], sum))) {
                while(r < sz) {
                    propagate(r);
                    r = (r << 1) + 1;
                    auto nxt = f(data[r], sum);
                    if(not check(nxt)) {
                        sum = nxt;
                        r--;
                    }
                }
                return r - sz;
            }
            sum = f(data[r], sum);
        } while((r & -r) != r);
        return -1;
    }
};

template <typename T, typename E, typename F, typename G, typename H>
LazySegmentTree<T, E, F, G, H> get_lazy_segment_tree(int N, const F &f, const G &g, const H &h, const T &ti, const E &ei) {
    return LazySegmentTree{N, f, g, h, ti, ei};
}

template <typename T, typename E, typename F, typename G, typename H>
LazySegmentTree<T, E, F, G, H> get_lazy_segment_tree(const vector<T> &v, const F &f, const G &g, const H &h, const T &ti, const E &ei) {
    return LazySegmentTree{v, f, g, h, ti, ei};
}

int main() {
    ll N, B, Q;
    cin >> N >> B >> Q;
    using mint = ArbitraryModInt;
    mint().set_mod(B);
    auto f = [](ll a, ll b){
        return a + b;
    };
    vm pX(Q + 1), pY(Q+ 1), pZ(Q + 1);
    pX[0] = pY[0] = pZ[0] = 1;
    rep(i, 1, Q + 1){
        pX[i] = pX[i - 1] + 1;
        pY[i] = mint(3) * pY[i - 1] + mint(2) * pX[i] * pZ[i - 1];
        pZ[i] = pZ[i - 1] * mint(3);
    }
    auto seg = get_lazy_segment_tree(N, f, f, f, 0LL, 0LL);
    rep(i, Q){
        ll L, M, R;
        cin >> L >> M >> R;
        L--, M--, R--;
        seg.apply(L, R + 1, 1LL);
        ll k = seg.get(M);
        cout << pX[k] << " " << pY[k] << " " << pZ[k] << endl;
    }
}
yukicoder

結果

テストケース

ソースコード
