結果
問題 | No.801 エレベーター |
ユーザー |
|
提出日時 | 2019-03-17 22:09:33 |
言語 | C++14 (gcc 11.2.0 + boost 1.78.0) |
結果 |
AC
|
実行時間 | 1,518 ms / 2,000 ms |
コード長 | 1,456 bytes |
コンパイル時間 | 1,397 ms |
使用メモリ | 6,952 KB |
最終ジャッジ日時 | 2023-02-11 07:46:38 |
合計ジャッジ時間 | 25,940 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
テストケース
テストケース表示入力 | 結果 | 実行時間 使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,900 KB |
testcase_01 | AC | 1 ms
6,948 KB |
testcase_02 | AC | 1 ms
4,900 KB |
testcase_03 | AC | 10 ms
4,904 KB |
testcase_04 | AC | 10 ms
6,948 KB |
testcase_05 | AC | 10 ms
4,904 KB |
testcase_06 | AC | 9 ms
6,948 KB |
testcase_07 | AC | 10 ms
4,904 KB |
testcase_08 | AC | 10 ms
4,900 KB |
testcase_09 | AC | 10 ms
4,900 KB |
testcase_10 | AC | 9 ms
4,904 KB |
testcase_11 | AC | 10 ms
4,900 KB |
testcase_12 | AC | 10 ms
6,948 KB |
testcase_13 | AC | 1,510 ms
6,948 KB |
testcase_14 | AC | 1,515 ms
6,948 KB |
testcase_15 | AC | 1,506 ms
6,948 KB |
testcase_16 | AC | 1,505 ms
4,904 KB |
testcase_17 | AC | 1,514 ms
4,904 KB |
testcase_18 | AC | 1,510 ms
4,900 KB |
testcase_19 | AC | 1,510 ms
4,904 KB |
testcase_20 | AC | 1,515 ms
6,948 KB |
testcase_21 | AC | 1,510 ms
4,904 KB |
testcase_22 | AC | 1,518 ms
4,904 KB |
testcase_23 | AC | 1,398 ms
4,904 KB |
testcase_24 | AC | 1,396 ms
4,900 KB |
testcase_25 | AC | 1,396 ms
4,900 KB |
testcase_26 | AC | 1,396 ms
4,904 KB |
testcase_27 | AC | 1,391 ms
4,904 KB |
testcase_28 | AC | 978 ms
6,952 KB |
ソースコード
#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 SegmentTree { std::vector<i64> seg; int sz = 1; SegmentTree(int n) { while(sz < n) sz <<= 1; seg.assign(sz * 2, 0); } void update(int k, int x = 1) { k += sz; seg[k] = x; while(k >>= 1) seg[k] = (seg[2 * k + 0] + seg[2 * k + 1]) % MOD; } void push(int k) { k += sz; while(k >>= 1) seg[k] = (seg[2 * k + 0] + seg[2 * k + 1]) % MOD; } void add(int k, int x) { k += sz; (seg[k] += x) %= MOD; } void build() { for(int i = 0; i < sz - 1; i++) (seg[i + sz + 1] += seg[i + sz] + MOD) %= MOD; for(int i = 0; i < sz; i++) push(i); } int get(int a, int b) { int L = 0, R = 0; for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) { if(a & 1) L = (L + seg[a++]) % MOD; if(b & 1) R = (seg[--b] + R) % MOD; } return (L + R) % MOD; } int operator[](int k) { return seg[k + sz]; } }; 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]--; } SegmentTree dp(n + 1); dp.update(0); for(int i = 0; i < k; i++) { SegmentTree to(n + 1); for(int j = 0; j < m; j++) { int tmp = dp.get(l[j], r[j]); to.add(l[j], tmp); to.add(r[j], -tmp); } to.build(); std::swap(dp, to); } printf("%d\n", dp[n - 1]); return 0; }