結果
問題 | No.2395 区間二次変換一点取得 |
ユーザー |
![]() |
提出日時 | 2023-07-28 22:16:37 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 66 ms / 2,000 ms |
コード長 | 23,433 bytes |
コンパイル時間 | 13,020 ms |
コンパイル使用メモリ | 300,896 KB |
最終ジャッジ日時 | 2025-02-15 20:32:42 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
ソースコード
// author: hotman78// date: 2023/07/28-22:16:29// --- begin raw code -----------------// #include"cpplib/util/template.hpp"// #include"cpplib/math/ACL_modint.hpp"// #include"cpplib/data_structure/binary_indexed_tree.hpp"// int main(){// lint n,b,q;// cin>>n>>b>>q;// mint::set_mod(b);// vector<tuple<mint,mint,mint>>ans={{1,1,1}};// rep(i,q){// auto [a,b,c]=ans.back();// ans.emplace_back(a+1,3*b+2*(a+1)*c,c*3);// }// BIT<lint>tb(n);// while(q--){// lint l,m,r;// cin>>l>>m>>r;// l--;// tb.add(l,1);// tb.add(r,-1);// int k=tb.sum(0,m);// auto [a,b,c]=ans[k];// cout<<a<<" "<<b<<" "<<c<<endl;// }// }// --- end raw code -----------------#line 2 "cpplib/util/template.hpp"#pragma GCC optimize("Ofast")#pragma GCC optimize("unroll-loops")#pragma GCC target("avx2")#include <bits/stdc++.h>using namespace std;#line 1 "cpplib/util/ioutil.hpp"// template <class Head,class... Args>// std::ostream& output(std::ostream& out,const Head& head,const Args&... args){// out>>head;// return output(head,args...);// }// template <class Head>// std::ostream& output(std::ostream& out,const Head& head){// out>>head;// return out;// }template <typename T, typename E>std::ostream &operator<<(std::ostream &out, std::pair<T, E> v) {out << "(" << v.first << "," << v.second << ")";return out;}// template <class... Args>// ostream& operator<<(ostream& out,std::tuple<Args...>v){// std::apply(output,v);// return out;// }#line 8 "cpplib/util/template.hpp"struct __INIT__ {__INIT__() {cin.tie(0);ios::sync_with_stdio(false);cout << fixed << setprecision(15);}} __INIT__;typedef long long lint;constexpr long long INF = 1LL << 60;constexpr int IINF = 1 << 30;constexpr double EPS = 1e-10;#ifndef REACTIVE#define endl '\n';#endiftypedef vector<lint> vec;typedef vector<vector<lint>> mat;typedef vector<vector<vector<lint>>> mat3;typedef vector<string> svec;typedef vector<vector<string>> smat;template <typename T> using V = vector<T>;template <typename T> using VV = V<V<T>>;template <typename T> inline void output(T t) {bool f = 0;for (auto i : t) {cout << (f ? " " : "") << i;f = 1;}cout << endl;}template <typename T> inline void output2(T t) {for (auto i : t)output(i);}template <typename T> inline void debug(T t) {bool f = 0;for (auto i : t) {cerr << (f ? " " : "") << i;f = 1;}cerr << endl;}template <typename T> inline void debug2(T t) {for (auto i : t)debug(i);}#define loop(n) for (long long _ = 0; _ < (long long)(n); ++_)#define _overload4(_1, _2, _3, _4, name, ...) name#define __rep(i, a) repi(i, 0, a, 1)#define _rep(i, a, b) repi(i, a, b, 1)#define repi(i, a, b, c) \for (long long i = (long long)(a); i < (long long)(b); i += c)#define rep(...) _overload4(__VA_ARGS__, repi, _rep, __rep)(__VA_ARGS__)#define _overload3_rev(_1, _2, _3, name, ...) name#define _rep_rev(i, a) repi_rev(i, 0, a)#define repi_rev(i, a, b) \for (long long i = (long long)(b)-1; i >= (long long)(a); --i)#define rrep(...) _overload3_rev(__VA_ARGS__, repi_rev, _rep_rev)(__VA_ARGS__)#define all(n) begin(n), end(n)template <typename T, typename E> bool chmin(T &s, const E &t) {bool res = s > t;s = min<T>(s, t);return res;}template <typename T, typename E> bool chmax(T &s, const E &t) {bool res = s < t;s = max<T>(s, t);return res;}const vector<lint> dx = {1, 0, -1, 0, 1, 1, -1, -1};const vector<lint> dy = {0, 1, 0, -1, 1, -1, 1, -1};#define SUM(v) accumulate(all(v), 0LL)#if __cplusplus >= 201703Ltemplate <typename T, typename... Args>auto make_vector(T x, int arg, Args... args) {if constexpr (sizeof...(args) == 0)return vector<T>(arg, x);elsereturn vector(arg, make_vector<T>(x, args...));}#endif#define extrep(v, ...) for (auto v : __MAKE_MAT__({__VA_ARGS__}))#define bit(n, a) ((n >> a) & 1)vector<vector<long long>> __MAKE_MAT__(vector<long long> v) {if (v.empty())return vector<vector<long long>>(1, vector<long long>());long long n = v.back();v.pop_back();vector<vector<long long>> ret;vector<vector<long long>> tmp = __MAKE_MAT__(v);for (auto e : tmp)for (long long i = 0; i < n; ++i) {ret.push_back(e);ret.back().push_back(i);}return ret;}using graph = vector<vector<int>>;template <typename T> using graph_w = vector<vector<pair<int, T>>>;#if __cplusplus >= 201703Lconstexpr inline long long powll(long long a, long long b) {long long res = 1;while (b--)res *= a;return res;}#endiftemplate <typename T, typename E>pair<T, E> &operator+=(pair<T, E> &s, const pair<T, E> &t) {s.first += t.first;s.second += t.second;return s;}template <typename T, typename E>pair<T, E> &operator-=(pair<T, E> &s, const pair<T, E> &t) {s.first -= t.first;s.second -= t.second;return s;}template <typename T, typename E>pair<T, E> operator+(const pair<T, E> &s, const pair<T, E> &t) {auto res = s;return res += t;}template <typename T, typename E>pair<T, E> operator-(const pair<T, E> &s, const pair<T, E> &t) {auto res = s;return res -= t;}#define BEGIN_STACK_EXTEND(size) \void *stack_extend_memory_ = malloc(size); \void *stack_extend_origin_memory_; \char *stack_extend_dummy_memory_ = (char *)alloca( \(1 + (int)(((long long)stack_extend_memory_) & 127)) * 16); \*stack_extend_dummy_memory_ = 0; \asm volatile("mov %%rsp, %%rbx\nmov %%rax, %%rsp" \: "=b"(stack_extend_origin_memory_) \: "a"((char *)stack_extend_memory_ + (size)-1024));#define END_STACK_EXTEND \asm volatile("mov %%rax, %%rsp" ::"a"(stack_extend_origin_memory_)); \free(stack_extend_memory_);#line 2 "cpplib/math/ACL_modint.hpp"#include <cassert>#include <numeric>#include <type_traits>#ifdef _MSC_VER#include <intrin.h>#endif#include <utility>#ifdef _MSC_VER#include <intrin.h>#endifnamespace atcoder {namespace internal {constexpr long long safe_mod(long long x, long long m) {x %= m;if (x < 0)x += m;return x;}struct barrett {unsigned int _m;unsigned long long im;explicit barrett(unsigned int m): _m(m), im((unsigned long long)(-1) / m + 1) {}unsigned int umod() const { return _m; }unsigned int mul(unsigned int a, unsigned int b) const {unsigned long long z = a;z *= b;#ifdef _MSC_VERunsigned long long x;_umul128(z, im, &x);#elseunsigned long long x =(unsigned long long)(((unsigned __int128)(z)*im) >> 64);#endifunsigned int v = (unsigned int)(z - x * _m);if (_m <= v)v += _m;return v;}};constexpr long long pow_mod_constexpr(long long x, long long n, int m) {if (m == 1)return 0;unsigned int _m = (unsigned int)(m);unsigned long long r = 1;unsigned long long y = safe_mod(x, m);while (n) {if (n & 1)r = (r * y) % _m;y = (y * y) % _m;n >>= 1;}return r;}constexpr bool is_prime_constexpr(int n) {if (n <= 1)return false;if (n == 2 || n == 7 || n == 61)return true;if (n % 2 == 0)return false;long long d = n - 1;while (d % 2 == 0)d /= 2;constexpr long long bases[3] = {2, 7, 61};for (long long a : bases) {long long t = d;long long y = pow_mod_constexpr(a, t, n);while (t != n - 1 && y != 1 && y != n - 1) {y = y * y % n;t <<= 1;}if (y != n - 1 && t % 2 == 0) {return false;}}return true;}template <int n> constexpr bool is_prime = is_prime_constexpr(n);constexpr std::pair<long long, long long> inv_gcd(long long a, long long b) {a = safe_mod(a, b);if (a == 0)return {b, 0};long long s = b, t = a;long long m0 = 0, m1 = 1;while (t) {long long u = s / t;s -= t * u;m0 -= m1 * u; // |m1 * u| <= |m1| * s <= bauto tmp = s;s = t;t = tmp;tmp = m0;m0 = m1;m1 = tmp;}if (m0 < 0)m0 += b / s;return {s, m0};}constexpr int primitive_root_constexpr(int m) {if (m == 2)return 1;if (m == 167772161)return 3;if (m == 469762049)return 3;if (m == 754974721)return 11;if (m == 998244353)return 3;int divs[20] = {};divs[0] = 2;int cnt = 1;int x = (m - 1) / 2;while (x % 2 == 0)x /= 2;for (int i = 3; (long long)(i)*i <= x; i += 2) {if (x % i == 0) {divs[cnt++] = i;while (x % i == 0) {x /= i;}}}if (x > 1) {divs[cnt++] = x;}for (int g = 2;; g++) {bool ok = true;for (int i = 0; i < cnt; i++) {if (pow_mod_constexpr(g, (m - 1) / divs[i], m) == 1) {ok = false;break;}}if (ok)return g;}}template <int m> constexpr int primitive_root = primitive_root_constexpr(m);unsigned long long floor_sum_unsigned(unsigned long long n,unsigned long long m,unsigned long long a,unsigned long long b) {unsigned long long ans = 0;while (true) {if (a >= m) {ans += n * (n - 1) / 2 * (a / m);a %= m;}if (b >= m) {ans += n * (b / m);b %= m;}unsigned long long y_max = a * n + b;if (y_max < m)break;n = (unsigned long long)(y_max / m);b = (unsigned long long)(y_max % m);std::swap(m, a);}return ans;}} // namespace internal} // namespace atcoder#include <cassert>#include <numeric>#include <type_traits>namespace atcoder {namespace internal {#ifndef _MSC_VERtemplate <class T>using is_signed_int128 =typename std::conditional<std::is_same<T, __int128_t>::value ||std::is_same<T, __int128>::value,std::true_type, std::false_type>::type;template <class T>using is_unsigned_int128 =typename std::conditional<std::is_same<T, __uint128_t>::value ||std::is_same<T, unsigned __int128>::value,std::true_type, std::false_type>::type;template <class T>using make_unsigned_int128 =typename std::conditional<std::is_same<T, __int128_t>::value, __uint128_t,unsigned __int128>;template <class T>using is_integral =typename std::conditional<std::is_integral<T>::value ||is_signed_int128<T>::value ||is_unsigned_int128<T>::value,std::true_type, std::false_type>::type;template <class T>using is_signed_int =typename std::conditional<(is_integral<T>::value &&std::is_signed<T>::value) ||is_signed_int128<T>::value,std::true_type, std::false_type>::type;template <class T>using is_unsigned_int =typename std::conditional<(is_integral<T>::value &&std::is_unsigned<T>::value) ||is_unsigned_int128<T>::value,std::true_type, std::false_type>::type;template <class T>using to_unsigned = typename std::conditional<is_signed_int128<T>::value, make_unsigned_int128<T>,typename std::conditional<std::is_signed<T>::value, std::make_unsigned<T>,std::common_type<T>>::type>::type;#elsetemplate <class T> using is_integral = typename std::is_integral<T>;template <class T>using is_signed_int =typename std::conditional<is_integral<T>::value && std::is_signed<T>::value,std::true_type, std::false_type>::type;template <class T>using is_unsigned_int =typename std::conditional<is_integral<T>::value &&std::is_unsigned<T>::value,std::true_type, std::false_type>::type;template <class T>using to_unsigned =typename std::conditional<is_signed_int<T>::value, std::make_unsigned<T>,std::common_type<T>>::type;#endiftemplate <class T>using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;template <class T>using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;template <class T> using to_unsigned_t = typename to_unsigned<T>::type;} // namespace internal} // namespace atcodernamespace atcoder {namespace internal {struct modint_base {};struct static_modint_base : modint_base {};template <class T> using is_modint = std::is_base_of<modint_base, T>;template <class T> using is_modint_t = std::enable_if_t<is_modint<T>::value>;} // namespace internaltemplate <int m, std::enable_if_t<(1 <= m)> * = nullptr>struct static_modint : internal::static_modint_base {using mint = static_modint;public:static constexpr int mod() { return m; }static mint raw(int v) {mint x;x._v = v;return x;}static_modint() : _v(0) {}template <class T, internal::is_signed_int_t<T> * = nullptr>static_modint(T v) {long long x = (long long)(v % (long long)(umod()));if (x < 0)x += umod();_v = (unsigned int)(x);}template <class T, internal::is_unsigned_int_t<T> * = nullptr>static_modint(T v) {_v = (unsigned int)(v % umod());}unsigned int val() const { return _v; }mint &operator++() {_v++;if (_v == umod())_v = 0;return *this;}mint &operator--() {if (_v == 0)_v = umod();_v--;return *this;}mint operator++(int) {mint result = *this;++*this;return result;}mint operator--(int) {mint result = *this;--*this;return result;}mint &operator+=(const mint &rhs) {_v += rhs._v;if (_v >= umod())_v -= umod();return *this;}mint &operator-=(const mint &rhs) {_v -= rhs._v;if (_v >= umod())_v += umod();return *this;}mint &operator*=(const mint &rhs) {unsigned long long z = _v;z *= rhs._v;_v = (unsigned int)(z % umod());return *this;}mint &operator/=(const mint &rhs) { return *this = *this * rhs.inv(); }mint operator+() const { return *this; }mint operator-() const { return mint() - *this; }mint pow(long long n) const {assert(0 <= n);mint x = *this, r = 1;while (n) {if (n & 1)r *= x;x *= x;n >>= 1;}return r;}mint inv() const {if (prime) {assert(_v);return pow(umod() - 2);} else {auto eg = internal::inv_gcd(_v, m);assert(eg.first == 1);return eg.second;}}friend mint operator+(const mint &lhs, const mint &rhs) {return mint(lhs) += rhs;}friend mint operator-(const mint &lhs, const mint &rhs) {return mint(lhs) -= rhs;}friend mint operator*(const mint &lhs, const mint &rhs) {return mint(lhs) *= rhs;}friend mint operator/(const mint &lhs, const mint &rhs) {return mint(lhs) /= rhs;}friend bool operator==(const mint &lhs, const mint &rhs) {return lhs._v == rhs._v;}friend bool operator!=(const mint &lhs, const mint &rhs) {return lhs._v != rhs._v;}private:unsigned int _v;static constexpr unsigned int umod() { return m; }static constexpr bool prime = internal::is_prime<m>;};template <int id> struct dynamic_modint : internal::modint_base {using mint = dynamic_modint;public:static int mod() { return (int)(bt.umod()); }static void set_mod(int m) {assert(1 <= m);bt = internal::barrett(m);}static mint raw(int v) {mint x;x._v = v;return x;}dynamic_modint() : _v(0) {}template <class T, internal::is_signed_int_t<T> * = nullptr>dynamic_modint(T v) {long long x = (long long)(v % (long long)(mod()));if (x < 0)x += mod();_v = (unsigned int)(x);}template <class T, internal::is_unsigned_int_t<T> * = nullptr>dynamic_modint(T v) {_v = (unsigned int)(v % mod());}unsigned int val() const { return _v; }mint &operator++() {_v++;if (_v == umod())_v = 0;return *this;}mint &operator--() {if (_v == 0)_v = umod();_v--;return *this;}mint operator++(int) {mint result = *this;++*this;return result;}mint operator--(int) {mint result = *this;--*this;return result;}mint &operator+=(const mint &rhs) {_v += rhs._v;if (_v >= umod())_v -= umod();return *this;}mint &operator-=(const mint &rhs) {_v += mod() - rhs._v;if (_v >= umod())_v -= umod();return *this;}mint &operator*=(const mint &rhs) {_v = bt.mul(_v, rhs._v);return *this;}mint &operator/=(const mint &rhs) { return *this = *this * rhs.inv(); }mint operator+() const { return *this; }mint operator-() const { return mint() - *this; }mint pow(long long n) const {assert(0 <= n);mint x = *this, r = 1;while (n) {if (n & 1)r *= x;x *= x;n >>= 1;}return r;}mint inv() const {auto eg = internal::inv_gcd(_v, mod());assert(eg.first == 1);return eg.second;}friend mint operator+(const mint &lhs, const mint &rhs) {return mint(lhs) += rhs;}friend mint operator-(const mint &lhs, const mint &rhs) {return mint(lhs) -= rhs;}friend mint operator*(const mint &lhs, const mint &rhs) {return mint(lhs) *= rhs;}friend mint operator/(const mint &lhs, const mint &rhs) {return mint(lhs) /= rhs;}friend bool operator==(const mint &lhs, const mint &rhs) {return lhs._v == rhs._v;}friend bool operator!=(const mint &lhs, const mint &rhs) {return lhs._v != rhs._v;}private:unsigned int _v;static internal::barrett bt;static unsigned int umod() { return bt.umod(); }};template <int id> internal::barrett dynamic_modint<id>::bt(998244353);using modint998244353 = static_modint<998244353>;using modint1000000007 = static_modint<1000000007>;using modint = dynamic_modint<-1>;namespace internal {template <class T>using is_static_modint = std::is_base_of<internal::static_modint_base, T>;template <class T>using is_static_modint_t = std::enable_if_t<is_static_modint<T>::value>;template <class> struct is_dynamic_modint : public std::false_type {};template <int id>struct is_dynamic_modint<dynamic_modint<id>> : public std::true_type {};template <class T>using is_dynamic_modint_t = std::enable_if_t<is_dynamic_modint<T>::value>;} // namespace internal} // namespace atcoderusing mint = atcoder::modint;#line 4 "cpplib/math/ACL_modint_base.hpp"std::ostream &operator<<(std::ostream &lhs, const mint &rhs) noexcept {lhs << rhs.val();return lhs;}std::istream &operator>>(std::istream &lhs, mint &rhs) noexcept {long long x;lhs >> x;rhs = x;return lhs;}int MOD_NOW = -1;int sz = 0;std::vector<mint> fact_table, fact_inv_table;void update(int x) {if (MOD_NOW != mint::mod() || sz == 0) {fact_table.assign(1, 1);fact_inv_table.assign(1, 1);sz = 1;MOD_NOW = mint::mod();}while (sz <= x) {fact_table.resize(sz * 2);fact_inv_table.resize(sz * 2);for (int i = sz; i < sz * 2; ++i) {fact_table[i] = fact_table[i - 1] * i;}fact_inv_table[sz * 2 - 1] = fact_table[sz * 2 - 1].inv();for (int i = sz * 2 - 2; i >= sz; --i) {fact_inv_table[i] = fact_inv_table[i + 1] * (i + 1);}sz *= 2;}}inline mint fact(int x) {assert(x >= 0);update(x);return fact_table[x];}inline mint fact_inv(int x) {assert(x >= 0);update(x);return fact_inv_table[x];}inline mint comb(int x, int y) {if (x < 0 || x < y || y < 0)return 0;return fact(x) * fact_inv(y) * fact_inv(x - y);}inline mint perm(int x, int y) { return fact(x) * fact_inv(x - y); }inline mint multi_comb(int x, int y) { return comb(x + y - 1, y); }#line 4 "cpplib/data_structure/binary_indexed_tree.hpp"/*** @brief BinaryIndexedTree*/template <typename T = long long, typename F = std::plus<T>,typename Inv = std::minus<T>>struct BIT {std::vector<T> bit;int n;F f;Inv inv;BIT(int n, T zero = T(), F f = F(), Inv inv = Inv()): n(n), f(f), inv(inv) {bit.resize(n + 1, zero);}// 0-indexed [0,x)-sumT sum(T x) {T res = 0;for (int i = x; i; i -= i & -i)res = f(res, bit[i]);return res;}// 0-indexed [x,y)-sumT sum(int x, int y) { return inv(sum(y), sum(x)); }// 0-indexedvoid add(int x, T val) {if (x >= n)return;for (int i = x + 1; i <= n; i += i & -i)bit[i] = f(bit[i], val);}};#line 4 "main.cpp"int main() {lint n, b, q;cin >> n >> b >> q;mint::set_mod(b);vector<tuple<mint, mint, mint>> ans = {{1, 1, 1}};rep(i, q) {auto [a, b, c] = ans.back();ans.emplace_back(a + 1, 3 * b + 2 * (a + 1) * c, c * 3);}BIT<lint> tb(n);while (q--) {lint l, m, r;cin >> l >> m >> r;l--;tb.add(l, 1);tb.add(r, -1);int k = tb.sum(0, m);auto [a, b, c] = ans[k];cout << a << " " << b << " " << c << endl;}}