結果

問題 No.801 エレベーター
コンテスト
ユーザー polylogK
提出日時 2019-03-17 21:48:58
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,060 bytes
コンパイル時間 1,937 ms
コンパイル使用メモリ 184,036 KB
実行使用メモリ 13,756 KB
最終ジャッジ日時 2024-07-07 21:43:17
合計ジャッジ時間 5,774 ms
ジャッジサーバーID
（参考情報） 		judge4 / 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 initial() {
		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);
	}
};

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]--;
	}
	
	std::vector<LazySegmentTree> dp(2, LazySegmentTree(n)); dp[0].update(0);
	for(int i = 0; i < k; i++) {
		int cur = i % 2, to = 1 - i % 2;
		dp[to].initial();
		for(int j = 0; j < m; j++) {
			int tmp = dp[cur].get(l[j], r[j]);
			dp[to].add(l[j], r[j], tmp);
		}
	}
	printf("%d\n", dp[k % 2][n - 1]);
	return 0;
}
0