結果

問題 No.801 エレベーター
コンテスト
ユーザー kappybar
提出日時 2020-05-01 12:16:13
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,638 bytes
コンパイル時間 2,359 ms
コンパイル使用メモリ 179,532 KB
実行使用メモリ 14,336 KB
最終ジャッジ日時 2024-12-23 18:00:59
合計ジャッジ時間 52,467 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 10 TLE * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
using ll =  long long ;
using P = pair<int,int> ;
using pll = pair<ll,ll>;
const int INF = 1e9;
const ll LINF = 1e18;
const int MOD = 1000000007;


struct LazySegmentTree{
        int n;
        vector<long long> node;
        vector<long long> lazy;
        ll inv2 = MOD -  (MOD / 2) % MOD;
        
        LazySegmentTree(vector<long long> v){
                int sz = v.size();
                n = 1;
                while(n < sz) n *= 2;
                node.resize(2*n-1,0);
                lazy.resize(2*n-1,0);
                for(int i=0;i<sz;i++) node[i+n-1] = v[i];
                for(int i=n-2;i>=0;i--) node[i] = (node[2*i+1] + node[2*i+2])%MOD;
        }

        void eval(int k){
            if(lazy[k] == 0) return;
            if(k < n - 1){
                lazy[2*k+1] = (lazy[2*k+1] + (lazy[k] * inv2)%MOD)%MOD;
                lazy[2*k+2] = (lazy[2*k+2] + (lazy[k] * inv2)%MOD)%MOD;
            }
            node[k] = (node[k] + lazy[k])%MOD;
            lazy[k] = 0;
        }
        
        //[a,b) の区間全てにxを足す。
        void update(int a,int b,long long x,int k=0,int l=0,int r=-1){
            eval(k);
            if(r < 0) r = n;
            if(a <= l && r <= b){
                lazy[k] = (lazy[k] + ((r - l) * x)%MOD)%MOD;
                eval(k);
            }else if(a < r && l < b){
                update(a,b,x,2*k+1,l,(l+r)/2);
                update(a,b,x,2*k+2,(l+r)/2,r);
                node[k] = (node[2*k+1] + node[2*k+2])%MOD;
            }
        }
        
        //[a,b) の区間の総和を求める。
        long long query(int a,int b,int k=0,int l=0,int r=-1){
            eval(k);
            if(r < 0) r = n;
            if(r <= a || b <= l) return 0;
            if(a <= l && r <= b) return node[k];
            long long vl = query(a,b,2*k+1,l,(l+r)/2);
            long long vr = query(a,b,2*k+2,(l+r)/2,r);
            return (vl + vr)%MOD;
        }
};

int main(){
    int n,m,k;
    cin >> n >> m >> k;
    vector<P> lr(m);
    rep(i,m){
        cin >> lr[i].first >> lr[i].second;
        --lr[i].first; --lr[i].second;
    }
    vector<ll> a(n,0);
    a[0] = 1;
    LazySegmentTree seg_prev(a);
    LazySegmentTree seg(vector<ll>(n,0));
    rep(i,k){
        rep(j,m){
            ll plus = seg_prev.query(lr[j].first,lr[j].second+1);
            seg.update(lr[j].first,lr[j].second+1,plus);
        }
        swap(seg,seg_prev);
        LazySegmentTree empty(vector<ll>(n,0));
        swap(empty,seg);
    }
    cout << seg_prev.query(n-1,n) << endl;
    return 0;
}
0