結果

問題 No.801 エレベーター
コンテスト
ユーザー polylogK
提出日時 2019-03-17 21:46:30
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,077 bytes
コンパイル時間 2,111 ms
コンパイル使用メモリ 180,840 KB
実行使用メモリ 10,752 KB
最終ジャッジ日時 2024-07-07 21:35:34
合計ジャッジ時間 5,774 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 10 TLE * 1 -- * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std::literals::string_literals;
using i64 = long long;
using std::cout;
using std::endl;
using std::cin;

const int MOD = 1e9 + 7;

struct LazySegmentTree {
	std::vector<int> seg, lazy;
	int sz = 1;
	
	LazySegmentTree(int n) {
		while(sz < n) sz <<= 1;
		seg.assign(sz * 2 - 1, 0);
		lazy.assign(sz * 2 - 1, 0);
	}
	void update(int k, int x = 1) {
		k += sz - 1;
		seg[k] = x;
		
		while(k) {
			k = (k - 1) >> 1;
			
			seg[k] = (seg[2 * k + 1] + seg[2 * k + 2]) % MOD;
		}
	}
	void push(int k, int l, int r) {
		if(k < sz - 1) {
			(lazy[2 * k + 1] += lazy[k]) %= MOD;
			(lazy[2 * k + 2] += lazy[k]) %= MOD;
		}
		(seg[k] += (i64)lazy[k] * (i64)(r - l) % MOD) %= MOD;
		lazy[k] = 0;
	}
	void add(int a, int b, int k, int l, int r, int x) {
		push(k, l, r);
		if(b <= l || r <= a) return;
		if(a <= l && r <= b) {
			(lazy[k] += x) %= MOD;
			push(k, l, r);
			return;
		}
		
		add(a, b, 2 * k + 1, l, (l + r) >> 1, x);
		add(a, b, 2 * k + 2, (l + r) >> 1, r, x);
		seg[k] = (seg[2 * k + 1] + seg[2 * k + 2]) % MOD;
	}
	void add(int a, int b, int x) {
		add(a, b, 0, 0, sz, x);
	}
	int get(int a, int b, int k, int l, int r) {
		push(k, l, r);
		if(b <= l || r <= a) return 0;
		if(a <= l && r <= b) return seg[k];
		
		int L = get(a, b, 2 * k + 1, l, (l + r) >> 1);
		int R = get(a, b, 2 * k + 2, (l + r) >> 1, r);
		return (L + R) % MOD;
	}
	int get(int a, int b) {
		return get(a, b, 0, 0, sz);
	}
	int operator[](int k) {
		return get(k, k + 1);
	}
};	

i64 pow_mod(i64 x, int n = MOD - 2) {
	i64 ret = 1;
	while(n) {
		if(n & 1) (ret *= x) %= MOD;
		(x *= x) %= MOD;
		n >>= 1;
	}
	return ret;
}

int main() {
	int n, m, k; scanf("%d%d%d", &n, &m, &k);
	std::vector<int> l(m), r(m);
	for(int i = 0; i < m; i++) {
		scanf("%d%d", &l[i], &r[i]);
		
		l[i]--;
	}
	
	LazySegmentTree dp(n), dp2(n); dp.update(0);
	for(int i = 0; i < k; i++) {
		dp2 = LazySegmentTree(n);
		for(int j = 0; j < m; j++) {
			int tmp = dp.get(l[j], r[j]);
			dp2.add(l[j], r[j], tmp);
		}
		std::swap(dp, dp2);
	}
	printf("%d\n", dp[n - 1]);
	return 0;
}
0