結果
問題 | No.2395 区間二次変換一点取得 |
ユーザー |
![]() |
提出日時 | 2023-07-28 21:34:50 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 260 ms / 2,000 ms |
コード長 | 999 bytes |
コンパイル時間 | 1,683 ms |
コンパイル使用メモリ | 170,316 KB |
実行使用メモリ | 6,272 KB |
最終ジャッジ日時 | 2024-10-06 17:53:33 |
合計ジャッジ時間 | 5,507 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
ソースコード
#include <bits/stdc++.h>using namespace std;struct binary_indexed_tree{int N;vector<int> BIT;binary_indexed_tree(int N): N(N), BIT(N + 1, 0){}int operator [](int i){i++;int ans = 0;while (i <= N){ans += BIT[i];i += i & -i;}return ans;}void add(int i, int x){while (i > 0){BIT[i] += x;i -= i & -i;}}void add(int L, int R, int x){add(L, -x);add(R, x);}};int main(){int N, B, Q;cin >> N >> B >> Q;vector<long long> dpX(Q + 1), dpY(Q + 1), dpZ(Q + 1);dpX[0] = 1;dpY[0] = 1;dpZ[0] = 1;for (int i = 0; i < Q; i++){dpX[i + 1] = (dpX[i] + 1) % B;dpY[i + 1] = (dpY[i] * 3 + 2 * dpX[i + 1] * dpZ[i]) % B;dpZ[i + 1] = dpZ[i] * 3 % B;}binary_indexed_tree BIT(N);for (int i = 0; i < Q; i++){int L, M, R;cin >> L >> M >> R;L--;M--;BIT.add(L, R, 1);int p = BIT[M];cout << dpX[p] << ' ' << dpY[p] << ' ' << dpZ[p] << endl;}}