結果

問題 No.2395 区間二次変換一点取得
ユーザー asaringoasaringo
提出日時 2023-07-28 22:36:12
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 240 ms / 2,000 ms
コード長 5,121 bytes
コンパイル時間 3,006 ms
コンパイル使用メモリ 215,948 KB
実行使用メモリ 8,192 KB
最終ジャッジ日時 2024-10-06 20:01:57
合計ジャッジ時間 6,193 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 3 ms
5,248 KB
testcase_09 AC 2 ms
5,248 KB
testcase_10 AC 2 ms
5,248 KB
testcase_11 AC 4 ms
5,248 KB
testcase_12 AC 21 ms
5,248 KB
testcase_13 AC 238 ms
8,192 KB
testcase_14 AC 237 ms
8,064 KB
testcase_15 AC 239 ms
8,064 KB
testcase_16 AC 240 ms
8,064 KB
testcase_17 AC 238 ms
7,936 KB
testcase_18 AC 168 ms
8,064 KB
testcase_19 AC 167 ms
8,064 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define overload2(a, b, c, ...) c
#define overload3(a, b, c, d, ...) d
#define overload4(a, b, c, d, e ...) e
#define overload5(a, b, c, d, e, f ...) f
#define overload6(a, b, c, d, e, f, g ...) g
#define fast_io ios::sync_with_stdio(false); cin.tie(nullptr);
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
typedef long long ll;
typedef long double ld;
#define chmin(a,b) a = min(a,b);
#define chmax(a,b) a = max(a,b);
#define bit_count(x) __builtin_popcountll(x)
#define leading_zero_count(x) __builtin_clz(x)
#define trailing_zero_count(x) __builtin_ctz(x)
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) a / gcd(a,b) * b
#define rep(...) overload3(__VA_ARGS__, rrep, rep1)(__VA_ARGS__)
#define rep1(i,n) for(int i = 0 ; i < n ; i++)
#define rrep(i,a,b) for(int i = a ; i < b ; i++)
#define repi(it,S) for(auto it = S.begin() ; it != S.end() ; it++)
#define pt(a) cout << a << endl;
#define print(...) printall(__VA_ARGS__);
#define debug(a) cout << #a << " " << a << endl;
#define all(a) a.begin(), a.end()
#define endl "\n";
#define v1(T,n,a) vector<T>(n,a)
#define v2(T,n,m,a) vector<vector<T>>(n,v1(T,m,a))
#define v3(T,n,m,k,a) vector<vector<vector<T>>>(n,v2(T,m,k,a))
#define v4(T,n,m,k,l,a) vector<vector<vector<vector<T>>>>(n,v3(T,m,k,l,a))
template<typename T,typename U>istream &operator>>(istream&is,pair<T,U>&p){is>>p.first>>p.second;return is;}
template<typename T,typename U>ostream &operator<<(ostream&os,const pair<T,U>&p){os<<p.first<<" "<<p.second;return os;}
template<typename T>istream &operator>>(istream&is,vector<T>&v){for(T &in:v){is>>in;}return is;}
template<typename T>ostream &operator<<(ostream&os,const vector<T>&v){for(auto it=v.begin();it!=v.end();){os<<*it<<((++it)!=v.end()?" ":"");}return os;}
template<typename T>istream &operator>>(istream&is,vector<vector<T>>&v){for(T &in:v){is>>in;}return is;}
template<typename T>ostream &operator<<(ostream&os,const vector<vector<T>>&v){for(auto it=v.begin();it!=v.end();){os<<*it<<((++it)!=v.end()?"\n":"");}return os;}
template<typename T>ostream &operator<<(ostream&os,const set<T>&v){for(auto it=v.begin();it!=v.end();){os<<*it<<((++it)!=v.end()?" ":"");}return os;}
template<typename T>ostream &operator<<(ostream&os,const multiset<T>&v){for(auto it=v.begin();it!=v.end();){os<<*it<<((++it)!=v.end()?" ":"");}return os;}
template<class... Args> void printall(Args... args){for(auto i:initializer_list<common_type_t<Args...>>{args...}) cout<<i<<" ";cout<<endl;}

template<typename T>
struct LazySegmentTree{
    private :
        const ll linf = 1e18 ;
        const int inf = 1e8 ;

        int n , n_ ;
        vector<T> dat , lazy ;

        void build(){
            n = 1 ;
            while(n < n_) n *= 2 ;
            dat.resize(2*n-1,0) ;
            lazy.resize(2*n-1,0) ;
        }

        // 遅延評価
        void eval(int k){
            dat[k] += lazy[k] ;
            if(k < n - 1){
                lazy[2 * k + 1] += lazy[k] / 2 ;
                lazy[2 * k + 2] += lazy[k] / 2 ;
            }
            lazy[k] = 0 ;
        }

        // 区間加算
        void add_(int a , int b , int k , int  l , int r , T w){
            eval(k) ;
            if(b <= l || r <= a) return ;
            if(a <= l && r <= b) {
                // 区間加算
                lazy[k] += (r - l) * w ;
                eval(k) ;
                return ;
            }
            add_(a,b,2*k+1,l,(l+r)/2,w) ;
            add_(a,b,2*k+2,(l+r)/2,r,w) ;
            // 区間の更新をする必要がある
            dat[k] = dat[2*k+1] + dat[2*k+2] ;
        }
        void add_(int a , int b , T x){
            return add_(a,b,0,0,n,x) ;
        }

        T query_(int a , int b , int k , int l , int r){
            //遅延評価（これは確実に必要）
            eval(k) ;
            if(b <= l || r <= a) return 0 ;
            if(a <= l && r <= b) return dat[k] ;
            T lef = query_(a,b,2*k+1,l,(l+r)/2) ;
            T rig = query_(a,b,2*k+2,(l+r)/2,r) ;
            return lef + rig ;
        }

        T query_(int a , int b){
            return query_(a,b,0,0,n)  ;
        }

    public :
        LazySegmentTree(int _n) : n_(_n) { build() ; }
        T query(int a , int b) { return query_(a,b) ; }
        void add(int a , int b , T x) { add_(a,b,x) ; }
};

ll mod;

ll powmod(ll x , ll n){
    ll res = 1 ;
    while(n > 0){
        if(n & 1) (res *= x) %= mod ;
        (x *= x) %= mod ;
        n >>= 1 ;
    }
    return res ;
}

void solve(){
    int n, q;
    cin >> n >> mod >> q;
    vector<ll> Q(q+1,0);
    Q[0] = 1;
    rrep(i,1,q+1){
        Q[i] = Q[i-1] * 3LL % mod + powmod(3,i-1) * (ll)(i + 1) * 2LL % mod;
        Q[i] %= mod;
    }
    LazySegmentTree<ll> segtree(n);
    rep(i,q){
        int l, r, m;
        cin >> l >> m >> r;
        l--;
        m--;
        segtree.add(l,r,1);
        ll v = segtree.query(m,m+1);
        ll a = (v + 1) % mod;
        ll b = Q[v];
        ll c = powmod(3,v);
        print(a,b,c)
    }
}

int main(){
    fast_io
    int t = 1;
    // cin >> t;
    rep(i,t) solve();
}
0