結果
問題 | No.2395 区間二次変換一点取得 |
ユーザー |
![]() |
提出日時 | 2023-07-29 00:57:47 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 85 ms / 2,000 ms |
コード長 | 16,271 bytes |
コンパイル時間 | 2,391 ms |
コンパイル使用メモリ | 218,024 KB |
最終ジャッジ日時 | 2025-02-15 20:49:42 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
ソースコード
#pragma region competitive_programming#ifdef __LOCAL#define _GLIBCXX_DEBUG#endif#pragma GCC optimize("Ofast")#include<bits/stdc++.h>//#include<atcoder/dsu>//#include "Rollback_dsu.hpp"//#include "Partial_Persistent_DSU.hpp"#include <algorithm>#include <cassert>#include <tuple>#include <vector>#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 atcodernamespace atcoder {long long pow_mod(long long x, long long n, int m) {assert(0 <= n && 1 <= m);if (m == 1) return 0;internal::barrett bt((unsigned int)(m));unsigned int r = 1, y = (unsigned int)(internal::safe_mod(x, m));while (n) {if (n & 1) r = bt.mul(r, y);y = bt.mul(y, y);n >>= 1;}return r;}long long inv_mod(long long x, long long m) {assert(1 <= m);auto z = internal::inv_gcd(x, m);assert(z.first == 1);return z.second;}std::pair<long long, long long> crt(const std::vector<long long>& r,const std::vector<long long>& m) {assert(r.size() == m.size());int n = int(r.size());long long r0 = 0, m0 = 1;for (int i = 0; i < n; i++) {assert(1 <= m[i]);long long r1 = internal::safe_mod(r[i], m[i]), m1 = m[i];if (m0 < m1) {std::swap(r0, r1);std::swap(m0, m1);}if (m0 % m1 == 0) {if (r0 % m1 != r1) return { 0, 0 };continue;}long long g, im;std::tie(g, im) = internal::inv_gcd(m0, m1);long long u1 = (m1 / g);if ((r1 - r0) % g) return { 0, 0 };long long x = (r1 - r0) / g % u1 * im % u1;r0 += x * m0;m0 *= u1; // -> lcm(m0, m1)if (r0 < 0) r0 += m0;}return { r0, m0 };}long long floor_sum(long long n, long long m, long long a, long long b) {assert(0 <= n && n < (1LL << 32));assert(1 <= m && m < (1LL << 32));unsigned long long ans = 0;if (a < 0) {unsigned long long a2 = internal::safe_mod(a, m);ans -= 1ULL * n * (n - 1) / 2 * ((a2 - a) / m);a = a2;}if (b < 0) {unsigned long long b2 = internal::safe_mod(b, m);ans -= 1ULL * n * ((b2 - b) / m);b = b2;}return ans + internal::floor_sum_unsigned(n, m, a, b);}} // namespace atcoder//#include "modint_plus.hpp"//typedef atcoder::modint1000000007 mint;//typedef atcoder::modint998244353 mint;//#include "Matrix.hpp"//#include<atcoder/convolution>//#include "Formal_Power_Series.hpp"//#include "Bit_Convolution.hpp"//#include<atcoder/maxflow>//#include<atcoder/mincostflow>//#include "Primal_Dual.hpp"//#include "maxflow_mincap.hpp"//#include<atcoder/fenwicktree>//#include<atcoder/segtree>//#include<atcoder/lazysegtree>//#include "2D_Segment_Tree.hpp"//#include "DisjointSparseTable.hpp"//#include "SWAG.hpp"//#include "Mo_algorithm.hpp"//#include "Heavy_Light_Decomposition.hpp"//#include "Binary_Trie.hpp"//#include "LCT.hpp"//#include "Slope_Trick.hpp"//#include<atcoder/string>//#include<atcoder/scc>namespace tomo0608 {typedef long long ll;typedef long double ld;template <class T> using V = std::vector<T>;template <class T> using VV = V<V<T>>;template <class T> using VVV = V<VV<T>>;typedef std::pair<int, int> pii;typedef std::pair<long long, long long> pll;template<class... T>void input(T&... a) { (std::cin >> ... >> a); };#define INT(...) int __VA_ARGS__; IN(__VA_ARGS__)#define LL(...) long long __VA_ARGS__; IN(__VA_ARGS__)#define STR(...) string __VA_ARGS__; IN(__VA_ARGS__)#define DBL(...) double __VA_ARGS__; IN(__VA_ARGS__)#define VEC(type, name, size) std::vector<type> name(size);IN(name)#define VECVEC(type, name, h, w) std::vector<std::vector<type>> name(h, std::vector<type>(w));IN(name)template<class T1, class T2> std::istream& operator>>(std::istream& is, std::pair<T1, T2>& p) { is >> p.first >> p.second; return is; }template<class T1, class T2> std::ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& p) { os << '(' << p.first << ", " << p.second <<')'; return os; }template<class T> std::istream& operator>>(std::istream& is, std::vector<T>& v) { for (auto& e : v) is >> e; return is; }template<class T> std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) { for (auto& e : v) os << e << ' '; return os; }template<typename T> std::ostream& operator << (std::ostream& os, std::set<T>& set_var) { os << "{"; for (auto itr = set_var.begin(); itr !=set_var.end(); itr++) { os << *itr;++itr;if (itr != set_var.end()) os << ", ";itr--; }os << "}";return os; }template <typename T, typename U> std::ostream& operator<<(std::ostream& os, std::map<T, U>& map_var) { os << "{";for (auto itr = map_var.begin(); itr != map_var.end(); itr++) { os << *itr;itr++;if (itr != map_var.end()) os << ", ";itr--; }os << "}";return os; }void IN() {}template <class Head, class... Tail> void IN(Head& head, Tail &...tail) {std::cin >> head;IN(tail...);}void print() { std::cout << '\n'; }template<class T, class... Ts>void print(const T& a, const Ts&... b) { std::cout << a; (std::cout << ... << (std::cout << ' ', b)); std::cout <<'\n'; }void drop() { std::cout << '\n';exit(0); }template<class T, class... Ts>void drop(const T& a, const Ts&... b) { std::cout << a; (std::cout << ... << (std::cout << ' ', b)); std::cout <<'\n';exit(0); }#ifdef __LOCALvoid debug_out() { std::cerr << std::endl; }template < class Head, class... Tail> void debug_out(Head H, Tail... T) { std::cerr << ' ' << H; debug_out(T...); }#define debug(...) std::cerr << 'L' << __LINE__ << " [" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)#define dump(x) std::cerr << 'L' << __LINE__ << " " << #x << " = " << (x) << std::endl#else#define debug(...) (void(0))#define dump(x) (void(0))#endif#define rep1(a) for(long long i = 0; i < a; i++)#define rep2(i, a) for(long long i = 0; i < a; i++)#define rep3(i, a, b) for(long long i = a; i < b; i++)#define rep4(i, a, b, c) for(long long i = a; i < b; i += c)#define drep1(a) for(long long i = a-1; i >= 0; i--)#define drep2(i, a) for(long long i = a-1; i >= 0; i--)#define drep3(i, a, b) for(long long i = a-1; i >= b; i--)#define drep4(i, a, b, c) for(long long i = a-1; i >= b; i -= c)#define overload4(a, b, c, d, e, ...) e#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)#define drep(...) overload4(__VA_ARGS__, drep4, drep3, drep2, drep1)(__VA_ARGS__)#define endl '\n'} // namespace tomo0608namespace tomo0608 {#define ALL(x) x.begin(),x.end()template <class T = long long, class S> T SUM(const S& v) { return accumulate(ALL(v), T(0)); }#define MIN(v) *min_element(ALL(v))#define MAX(v) *max_element(ALL(v))#define SORT(v) sort(ALL(v))#define REVERSE(v) reverse(ALL(v))#define RSORT(v) sort(ALL(v)); reverse(ALL(v))#define UNIQUE(x) SORT(x), x.erase(unique(ALL(x)), x.end())#define lb(c, x) distance((c).begin(), lower_bound(ALL(c), (x)))#define ub(c, x) distance((c).begin(), upper_bound(ALL(c), (x)))template <typename T> void zip(std::vector<T>& x) { std::vector<T> y = x;UNIQUE(y);for (int i = 0; i < x.size(); ++i) { x[i] = lb(y, x[i]); } }template<class T> using priority_queue_rev = std::priority_queue<T, std::vector<T>, std::greater<T>>;template<class T, class U> inline bool chmax(T& a, const U& b) { if (a < b) { a = b; return 1; } return 0; }template<class T, class U> inline bool chmin(T& a, const U& b) { if (a > b) { a = b; return 1; } return 0; }template<class T> inline int count_between(std::vector<T>& a, T l, T r) { return lower_bound(ALL(a), r) - lower_bound(ALL(a), l); } // [l, r)#define bittest(n, k) (((n) >> k) & 1)int topbit(signed t) { return t == 0 ? -1 : 31 - __builtin_clz(t); }int topbit(long long t) { return t == 0 ? -1 : 63 - __builtin_clzll(t); }int lowbit(signed a) { return a == 0 ? 32 : __builtin_ctz(a); }int lowbit(long long a) { return a == 0 ? 64 : __builtin_ctzll(a); }#define perm(v) for(bool permrepflag = true; (permrepflag ? exchange(permrepflag, false) : next_permutation(ALL(v)));)template <typename T, typename S> T ceil(T x, S y) {assert(y);return (y < 0 ? ceil(-x, -y) : (x > 0 ? (x + y - 1) / y : x / y));}template <typename T, typename S> T floor(T x, S y) {assert(y);return (y < 0 ? floor(-x, -y) : (x > 0 ? x / y : x / y - (x % y == 0 ? 0 : 1)));}}using namespace atcoder;using namespace std;using namespace tomo0608;int dx[8] = { 1, 0, -1, 0, 1, 1, -1, -1 };int dy[8] = { 0, 1, 0, -1, 1, -1, -1, 1 };// インタラクティブ問題のときは出力するたびにcout.flush();を忘れない!!!!!void solve();int main() {std::cin.tie(0);std::ios_base::sync_with_stdio(false);std::cout << std::setprecision(20);int codeforces = 1;//cin >> codeforces;while (codeforces--) {solve();}return 0;}#pragma endregiontemplate<class T>struct Binary_Indexed_Tree {public:Binary_Indexed_Tree() :_n(0) {}Binary_Indexed_Tree(int n) : _n(n) {for (int i = 0; i < 2; i++)data[i].assign(n, 0);}void add(int l, int r, T x) { // [l, r)にxを加算assert(0 <= l && l < r && r <= _n);add_sub(0, l, -x * (l - 1));add_sub(0, r, x * (r - 1));add_sub(1, l, x);add_sub(1, r, -x);}void add(int p, T x) { // pにxを加算assert(0 <= p && p < _n);add(p, p + 1, x);}T sum(int r) { // [0, r)return sum_sub(0, r) + sum_sub(1, r) * (r - 1);}T sum(int l, int r) { // [l,r)assert(0 <= l && l <= r && r <= _n);return sum(r) - sum(l);}T operator[](int r) { return sum(r + 1) - sum(r); }int lower_bound(T w) { // \sum_{i=0}^{x}a_x >= wとなるような最小のx なければn, ただしa_xは全て非負であることが条件if (w <= 0)return 0;int x = 0, r = 1;while (r < _n)r = r << 1;for (int len = r; len > 0; len = len >> 1) {if (x + len < _n && sum(x, x + len) < w) {w -= sum(x, x + len);x += len;}}if (w > 0)x++;return x;}private:int _n;std::vector<T> data[2];void add_sub(int i, int p, T x) { // 0-indexedassert(0 <= p && p <= _n);p++; // 内部では1-indexedwhile (p <= _n) {data[i][p - 1] += x;p += p & -p;}}T sum_sub(int i, int p) {T s = 0;for (int idx = p; idx > 0; idx -= (idx & -idx)) {s += data[i][idx - 1];}return s;}};void solve() {LL(n, b, q);Binary_Indexed_Tree<ll> BIT(n + 1);while (q--) {LL(l, m, r);BIT.add(l, r + 1, 1);ll cnt = BIT[m];ll x = (cnt + 1) % b, z = pow_mod(3, cnt, b), y = cnt * cnt + 3 * cnt + 3;y %= b;y *= pow_mod(3, cnt - 1, b);y %= b;print(x, y, z);}}