結果
問題 | No.2395 区間二次変換一点取得 |
ユーザー |
![]() |
提出日時 | 2023-07-28 21:38:33 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 293 ms / 2,000 ms |
コード長 | 2,659 bytes |
コンパイル時間 | 2,824 ms |
コンパイル使用メモリ | 249,492 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-06 18:01:15 |
合計ジャッジ時間 | 6,886 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
ソースコード
#include<bits/stdc++.h>using namespace std;using ll = long long;ll mod = 998'244'353;//const ll mod = 1'000'000'007;//const ll mod = 67'280'421'310'721;struct mint{long long x;mint(long long x=0):x((x%mod+mod)%mod){}mint operator-() const{return mint(-x);}mint& operator+=(const mint& a){if((x+=a.x)>=mod)x-=mod;return *this;}mint& operator-=(const mint& a){if((x+=mod-a.x)>=mod)x-=mod;return *this;}mint& operator*=(const mint& a){(x *= a.x) %= mod;return *this;}mint operator+(const mint& a) const{mint res(*this);return res+=a;}mint operator-(const mint& a) const{mint res(*this);return res-=a;}mint operator*(const mint& a) const{mint res(*this);return res*=a;}mint pow(long long n) const {assert(0 <= n);mint a = *this, r = 1;while (n) {if (n & 1) r *= a;a *= a;n >>= 1;}return r;}mint inv() const{return pow(mod-2);}mint& operator/=(const mint& a){return (*this)*=a.inv();}mint operator/(const mint& a) const {mint res(*this);return res/=a;}friend ostream& operator<<(ostream& os, const mint& m){os << m.x;return os;}bool operator==(const mint& a) const {return x == a.x;}bool operator<(const mint& a) const{return x < a.x;}};template< typename T >struct BIT{int n;vector<T> data;BIT(int n):n(n),data(n+1,0){}void add(int i,T x){i++;while(i<=n){data[i] += x;i += i & (-i);}}//sum of [l,r)T sum(int l,int r){return sum(r-1)-sum(l-1);}T sum(int i){i++;T now = 0;while(i>0){now += data[i];i -= i & (-i);}return now;}};int main(){cin.tie(nullptr);ios::sync_with_stdio(false);ll n,q;cin>>n>>mod>>q;BIT<ll> bit(n+1);vector<mint> sum(q+5,0);for(int i = 1;i<=q+4;i++) sum[i] += sum[i-1] + i;while(q--){ll l,m,r;cin>>l>>m>>r;l--;bit.add(l,1);bit.add(r,-1);m--;ll cnt = bit.sum(0,m+1);mint x = 1 + cnt;mint z = mint(3).pow(cnt);mint y = mint(3).pow(cnt);if(cnt){y += mint(2) * mint(3).pow(cnt-1) * (sum[cnt+1] - mint(1));}cout<<x<<" "<<y<<" "<<z<<endl;}}