結果
問題 | 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; }