結果
問題 | No.2395 区間二次変換一点取得 |
ユーザー |
|
提出日時 | 2023-08-02 08:07:01 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 450 ms / 2,000 ms |
コード長 | 1,489 bytes |
コンパイル時間 | 1,737 ms |
コンパイル使用メモリ | 172,296 KB |
実行使用メモリ | 7,296 KB |
最終ジャッジ日時 | 2024-10-12 03:06:14 |
合計ジャッジ時間 | 6,625 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
ソースコード
#include <bits/stdc++.h>#include <iterator>using namespace std;#define rep(i, n) for(int i=0; i<n; i++)#define debug 1using ll = long long;using ld = long double;const int mod = 998244353;const double pi = atan2(0, -1);#include <time.h>#include <chrono>ll Power(ll x, ll y, ll B) {if (y == 0) {return 1;}if (y == 1) {return x % B;}if (y % 2 == 1) {return (Power(x, y - 1, B) * (x % B)) % B;}else {ll t = Power(x, y / 2, B) % B;return (t*t)%B;}}ll N, B;ll n = 1;struct SegTree {vector<ll> Tree;SegTree() {while (n < N) {n *= 2;}vector<ll> t(n*2, 0);Tree = t;}void Add(int l, int r){AddFunc(l, r, 0, 0, n);}void AddFunc(int l, int r, int k, int s, int t) {if (r<=s || l>=t) {return;}else if (l <= s && r >= t) {Tree[k]++;}else {AddFunc(l, r, k * 2 + 1, s, (s+t) / 2);AddFunc(l, r, k * 2 + 2, (s+t) / 2, t);}}int Query(int m) {int ans = 0;int p = m + n - 1;while (p>0) {ans += Tree[p];p = (p - 1) / 2;}ans += Tree[0];return ans;}};int main() {int Q;cin >> N >> B >> Q;SegTree tree;rep(test, Q) {int L, M, R;cin >> L >> M >> R;L--; M--;tree.Add(L, R);int num = tree.Query(M);ll X, Y, Z;X = (num + 1)%B;Z = Power(3, num, B)%B;if (num == 0) {Y = 1;}else {Y = (Power(3, num, B) + Power(3, num - 1, B) * (ll)num % B * ((ll)num + 3)%B) % B;}cout << X << " " << Y << " " << Z << endl;}}