結果
問題 | No.2395 区間二次変換一点取得 |
ユーザー |
![]() |
提出日時 | 2023-07-28 22:05:10 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 81 ms / 2,000 ms |
コード長 | 3,134 bytes |
コンパイル時間 | 1,116 ms |
コンパイル使用メモリ | 112,900 KB |
最終ジャッジ日時 | 2025-02-15 20:27:36 |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
ソースコード
// #pragma GCC target("avx2") // #pragma GCC optimize("O3") // #pragma GCC optimize("unroll-loops") #include <algorithm> #include <bitset> #include <cassert> #include <cmath> #include <complex> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <string> #include <tuple> #include <vector> #define _USE_MATH_DEFINES #include <math.h> using namespace std; using lg = long long; using pii = pair<int, int>; using pll = pair<lg, lg>; #define TEST cerr << "TEST" << endl #define IINF 2147483647 #define LLINF 9223372036854775807LL // #define AMARI 998244353 #define AMARI 1000000007 #define TEMOTO ((sizeof(long double) == 16) ? false : true) #define TIME_LIMIT 1980 * (TEMOTO ? 1 : 1000) #define el '\n' #define El '\n' #define mpr make_pair template<typename T> class ococo_segtree { T func(T a, T b) { //ここに演算を入れる return (a + b); } public: int n; T tmax; //range minimum query vector<T> rmq; //(データの大きさ,単位元) ococo_segtree(int N = 0, T t = IINF) { syokica(N, t); } //配列の初期化 O(N) void syokica(int a, T t) { n = 1; tmax = t; while (n < a)n *= 2; rmq.resize(2 * n - 1); for (int i = 0; i < 2 * n - 1; i++) { rmq[i] = tmax; } } //a[i]をxにする O(logN) void update_num(int i, T x) { i += (n - 1); rmq[i] = x; while (i) { i = (i - 1) / 2; rmq[i] = func(rmq[i * 2 + 1], rmq[i * 2 + 2]); } } //a[i]にxを加える O(logN) void add_num(int i, T x) { i += (n - 1); rmq[i] = func(rmq[i], x); while (i) { i = (i - 1) / 2; rmq[i] = func(rmq[i * 2 + 1], rmq[i * 2 + 2]); } } T get_minimum2(int a, int b, int k, int l, int r) { if (a <= l && r <= b)return rmq[k]; else if (r <= a || b <= l)return tmax; else return func(get_minimum2(a, b, k * 2 + 1, l, (l + r) / 2), get_minimum2(a, b, k * 2 + 2, (l + r) / 2, r)); } //[l,r)の区間演算の取得 O(logN) T get_val(int l, int r) { return get_minimum2(l, r, 0, 0, n); } }; #define MULTI_TEST_CASE false void solve(void) { int n,b,q; cin >> n >> b >> q; vector<lg> x(q + 1),y(q + 1),z(q + 1); x[0] = y[0] = z[0] = 1; for(int i = 1; i <= q; i++){ x[i] = x[i - 1] + 1; x[i] %= b; y[i] = 3 * y[i - 1] + 2 * x[i] * z[i - 1]; y[i] %= b; z[i] = z[i - 1] * 3; z[i] %= b; } ococo_segtree<int> ruiseki(n + 1,0); for(int i = 0; i < q; i++){ int l,m,r; cin >> l >> m >> r; l--; m--; r--; ruiseki.add_num(l,1); ruiseki.add_num(r + 1,-1); int idx = ruiseki.get_val(0,m + 1); cout << x[idx] << ' ' << y[idx] << ' ' << z[idx] << el; } return; } void calc(void){ return; } int main(void) { cin.tie(nullptr); ios::sync_with_stdio(false); calc(); int t = 1; if (MULTI_TEST_CASE) cin >> t; while (t--) { solve(); } return 0; }