結果

問題 No.801 エレベーター
コンテスト
ユーザー eto_nagisa
提出日時 2019-03-18 05:23:18
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,523 bytes
コンパイル時間 1,919 ms
コンパイル使用メモリ 180,624 KB
実行使用メモリ 10,624 KB
最終ジャッジ日時 2024-07-08 13:19:16
合計ジャッジ時間 6,003 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 10 TLE * 1 -- * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"

#define REP(i,n) for(ll i=0;i<ll(n);++i)
#define RREP(i,n) for(ll i=ll(n)-1;i>=0;--i)
#define FOR(i,m,n) for(ll i=m;i<ll(n);++i)
#define RFOR(i,m,n) for(ll i=ll(n)-1;i>=ll(m);--i)
#define ALL(v) (v).begin(),(v).end()
#define UNIQUE(v) v.erase(unique(ALL(v)),v.end());
#define INF 1000000001ll
#define MOD 1000000007ll
#define EPS 1e-9

constexpr int dx[8] = { 1,1,0,-1,-1,-1,0,1 };
constexpr int dy[8] = { 0,1,1,1,0,-1,-1,-1 };


using namespace std;

using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

template <class T> bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
template <class T> bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }


#include "bits/stdc++.h"

struct RARS {
	struct t1 {
		long long val, size;
		constexpr t1(long long v, long long s) :val(v%MOD), size(s%MOD) {}
	};
	using t2 = long long;
	static constexpr t1 id1() {
		return t1(0, 1);
	}
	static constexpr t2 id2() {
		return 0ll;
	}
	static t1 op1(const t1 &a, const t1 &b) {
		return t1((a.val + b.val) % MOD, (a.size + b.size) % MOD);
	}
	static t1 op2(const t1 &a, const t2 &b) {
		return t1((a.val + b * a.size) % MOD, a.size);
	}
	static t2 op3(const t2 &a, const t2 &b) {
		return (a + b) % MOD;
	}
};

template<typename M>
struct LazySegmentTree {

	int n;
	using T1 = typename M::t1;
	using T2 = typename M::t2;
	std::vector<T1> nodes;
	std::vector<T2> lazy;

	LazySegmentTree(std::vector<T1> v) {
		int sz = (int)v.size();
		n = 1; while (n < sz) n *= 2;
		nodes.resize(2 * n - 1, M::id1());
		lazy.resize(2 * n - 1, M::id2());

		for (int i = 0; i < sz; i++) nodes[i + n - 1] = v[i];
		for (int i = n - 2; i >= 0; i--) nodes[i] = M::op1(nodes[i * 2 + 1], nodes[i * 2 + 2]);
	}

	LazySegmentTree(int _n) {
		int sz = _n;
		n = 1; while (n < sz) n *= 2;
		nodes.resize(2 * n - 1, M::id1());
		lazy.resize(2 * n - 1, M::id2());

		for (int i = n - 2; i >= 0; i--) nodes[i] = M::op1(nodes[i * 2 + 1], nodes[i * 2 + 2]);
	}

	void eval(int k, int l, int r) {
		if (lazy[k] != M::id2()) {
			nodes[k] = M::op2(nodes[k], lazy[k]);
			if (r - l > 1) {
				lazy[2 * k + 1] = M::op3(lazy[2 * k + 1], lazy[k]);
				lazy[2 * k + 2] = M::op3(lazy[2 * k + 2], lazy[k]);
			}
			lazy[k] = M::id2();
		}
	}
	void update(int a, int b, T2 x) {
		update(a, b, x, 0, 0, n);
	}
	T1 query(int a, int b) {
		return query(a, b, 0, 0, n);
	}
private:
	void update(int a, int b, T2 x, int k, int l, int r) {
		eval(k, l, r);
		if (b <= l || r <= a)return;
		if (a <= l && r <= b) {
			lazy[k] = M::op3(lazy[k], x);
			eval(k, l, r);
		}
		else {
			update(a, b, x, 2 * k + 1, l, (l + r) / 2);
			update(a, b, x, 2 * k + 2, (l + r) / 2, r);
			nodes[k] = M::op1(nodes[2 * k + 1], nodes[2 * k + 2]);
		}
	}

	T1 query(int a, int b, int k, int l, int r) {
		if (b <= l || r <= a)return M::id1();
		eval(k, l, r);
		if (a <= l && r <= b)return nodes[k];
		return M::op1(query(a, b, 2 * k + 1, l, (l + r) / 2), query(a, b, 2 * k + 2, (l + r) / 2, r));
	}
};
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, m, k;
	cin >> n >> m >> k;
	vi l(m), r(m);
	REP(i, m) {
		cin >> l[i] >> r[i];
		l[i]--;
	}
	using Lseg = LazySegmentTree<RARS>;
	LazySegmentTree<RARS> st(n);
	st.update(0, 1, 1);
	REP(i, k) {
		Lseg next(n);
		REP(j, m) {
			next.update(l[j], r[j], st.query(l[j], r[j]).val);
		}
		st = move(next);
	}
	cout << st.query(n - 1, n).val << endl;

}
0