結果
問題 | No.801 エレベーター |
ユーザー |
![]() |
提出日時 | 2019-03-17 22:07:49 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,352 ms / 2,000 ms |
コード長 | 1,578 bytes |
コンパイル時間 | 1,954 ms |
コンパイル使用メモリ | 204,592 KB |
最終ジャッジ日時 | 2025-01-06 23:02:29 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h>using namespace std;using i64 = int64_t;using vi = vector<i64>;using vvi = vector<vi>;constexpr i64 MOD = 1e9 + 7;class BIT {int n;vi data0, data1;void add(vi& data, int i, i64 x) {while (i <= n) {data[i] += x;data[i] %= MOD;i += i & -i;}}i64 sum(vi& data, int i) {i64 s = 0;while (i > 0) {s += data[i];s %= MOD;i -= i & -i;}return s;}public:BIT(int n) : n(n) {data0 = vi(n + 1);data1 = vi(n + 1);}// [l, r)void add(int l, int r, i64 x) {l++;r++;add(data0, l, -x * (l - 1) % MOD);add(data1, l, x);add(data0, r, x * (r - 1) % MOD);add(data1, r, -x);}// [l, r)i64 sum(int l, int r) {i64 s = 0;s += sum(data0, r) + sum(data1, r) * r;s -= sum(data0, l) + sum(data1, l) * l;return s % MOD;}};int main() {int n, m, k;cin >> n >> m >> k;vector<pair<int, int>> lrs;for (int i = 0; i < m; i++) {int l, r;cin >> l >> r;l--;lrs.emplace_back(l, r);}vector<BIT> dp(k + 1, BIT(n));dp[0].add(0, 1, 1);for (int i = 0; i < k; i++) {for (int j = 0; j < m; j++) {i64 s = dp[i].sum(lrs[j].first, lrs[j].second);dp[i + 1].add(lrs[j].first, lrs[j].second, s);}}cout << (dp[k].sum(n - 1, n) % MOD + MOD) % MOD << endl;}