結果

問題 No.801 エレベーター
ユーザー polylogKpolylogK
提出日時 2019-03-17 21:46:30
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 2,077 bytes
コンパイル時間 1,975 ms
コンパイル使用メモリ 179,656 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-22 04:52:10
合計ジャッジ時間 7,946 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 63 ms
4,380 KB
testcase_04 AC 63 ms
4,376 KB
testcase_05 AC 61 ms
4,376 KB
testcase_06 AC 61 ms
4,380 KB
testcase_07 AC 63 ms
4,380 KB
testcase_08 AC 65 ms
4,376 KB
testcase_09 AC 62 ms
4,376 KB
testcase_10 AC 63 ms
4,380 KB
testcase_11 AC 61 ms
4,376 KB
testcase_12 AC 63 ms
4,380 KB
testcase_13 TLE -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
権限があれば一括ダウンロードができます

ソースコード

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