結果
問題 | No.2395 区間二次変換一点取得 |
ユーザー |
👑 |
提出日時 | 2023-07-28 23:12:53 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 341 ms / 2,000 ms |
コード長 | 909 bytes |
コンパイル時間 | 1,798 ms |
コンパイル使用メモリ | 176,388 KB |
実行使用メモリ | 5,632 KB |
最終ジャッジ日時 | 2024-10-06 21:17:22 |
合計ジャッジ時間 | 6,006 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
ソースコード
#include <bits/stdc++.h>using namespace std;#include "atcoder/modint"#include "atcoder/lazysegtree"using namespace atcoder;using mint=modint;using S=int;using F=pair<int,int>;S op(S a, S b){return a+b;}S e(){return 0;}S mapping(F f, S x){return f.first*x+f.second;}F composition(F f, F g){return make_pair(f.first*g.first,f.first*g.second+f.second);}F id(){return make_pair(1,0);}int main(void) {int n,b,q;cin >> n >> b >> q;mint::set_mod(b);vector<S> v(n,1);lazy_segtree<S,op,e,F,mapping,composition,id> s(v);while(q--){int l,m,r;cin >> l >> m >> r;--l;--m;--r;s.apply(l,r+1,make_pair(1,1));auto ans=s.get(m);cout << mint(ans).val() << " " << (mint(3).pow(ans-2)*(mint(ans)*ans+ans+1)).val() << " " << (mint(3).pow(ans-1)).val() << endl;}return 0;}