結果
問題 | No.992 最長増加部分列の数え上げ |
ユーザー | Y17 |
提出日時 | 2020-02-14 22:23:57 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 294 ms / 2,000 ms |
コード長 | 2,244 bytes |
コンパイル時間 | 2,255 ms |
コンパイル使用メモリ | 156,464 KB |
実行使用メモリ | 18,340 KB |
最終ジャッジ日時 | 2023-07-28 18:34:32 |
合計ジャッジ時間 | 12,416 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge15 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,376 KB |
testcase_01 | AC | 2 ms
4,376 KB |
testcase_02 | AC | 2 ms
4,376 KB |
testcase_03 | AC | 1 ms
4,380 KB |
testcase_04 | AC | 104 ms
9,836 KB |
testcase_05 | AC | 75 ms
6,560 KB |
testcase_06 | AC | 131 ms
9,856 KB |
testcase_07 | AC | 90 ms
9,748 KB |
testcase_08 | AC | 48 ms
6,532 KB |
testcase_09 | AC | 95 ms
9,680 KB |
testcase_10 | AC | 131 ms
9,796 KB |
testcase_11 | AC | 166 ms
9,976 KB |
testcase_12 | AC | 30 ms
4,856 KB |
testcase_13 | AC | 86 ms
9,684 KB |
testcase_14 | AC | 93 ms
9,804 KB |
testcase_15 | AC | 31 ms
4,804 KB |
testcase_16 | AC | 263 ms
17,000 KB |
testcase_17 | AC | 47 ms
6,456 KB |
testcase_18 | AC | 86 ms
9,844 KB |
testcase_19 | AC | 162 ms
9,900 KB |
testcase_20 | AC | 294 ms
17,940 KB |
testcase_21 | AC | 292 ms
17,208 KB |
testcase_22 | AC | 286 ms
17,716 KB |
testcase_23 | AC | 287 ms
17,412 KB |
testcase_24 | AC | 286 ms
16,592 KB |
testcase_25 | AC | 286 ms
16,640 KB |
testcase_26 | AC | 289 ms
16,732 KB |
testcase_27 | AC | 290 ms
16,324 KB |
testcase_28 | AC | 288 ms
17,292 KB |
testcase_29 | AC | 294 ms
16,320 KB |
testcase_30 | AC | 208 ms
16,988 KB |
testcase_31 | AC | 211 ms
17,908 KB |
testcase_32 | AC | 210 ms
18,080 KB |
testcase_33 | AC | 209 ms
17,112 KB |
testcase_34 | AC | 204 ms
17,392 KB |
testcase_35 | AC | 200 ms
16,564 KB |
testcase_36 | AC | 190 ms
17,404 KB |
testcase_37 | AC | 201 ms
17,152 KB |
testcase_38 | AC | 211 ms
16,904 KB |
testcase_39 | AC | 192 ms
17,016 KB |
testcase_40 | AC | 205 ms
17,284 KB |
testcase_41 | AC | 205 ms
16,944 KB |
testcase_42 | AC | 205 ms
18,016 KB |
testcase_43 | AC | 207 ms
17,028 KB |
testcase_44 | AC | 207 ms
18,340 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; template <class Monoid> struct SegmentTree{ using Func = function<Monoid(Monoid, Monoid)>; int size; vector<Monoid> seg; const Func merge; const Monoid def; SegmentTree(int n, Monoid d, const Func f): merge(f), def(d){ for(size = 1; size <= n; size <<= 1); seg.assign(size*2, def); } Monoid& operator[] (int i) { return seg[i+size]; }; void build(){ for(int i = size-1;i >= 0;i--) seg[i] = merge(seg[i*2], seg[i*2+1]); } void update(int i, Monoid val){ seg[i += size] = val; while(i >>= 1) seg[i] = merge(seg[i*2], seg[i*2+1]); } void add(int i, Monoid val){ update(i, val+seg[i+size]); } Monoid get(int a, int b){ Monoid l = def, r = def; for(a += size, b += size; a < b; a >>= 1, b >>= 1){ if(a & 1) l = merge(l, seg[a++]); if(b & 1) r = merge(r, seg[--b]); } return merge(l, r); } }; #define int long long #define MOD 1000000007 typedef pair<int, int> P; signed main(){ int n; cin >> n; SegmentTree<P> seg(n, {0, 0}, [](P a, P b){ if(a.first > b.first){ return a; }else if(a.first < b.first){ return b; } a.second += b.second; a.second %= MOD; return a; }); int a[200010]; vector<pair<int, int>> azip; for(int i = 0;i < n;i++){ int b; cin >> b; a[i] = b; azip.push_back({b, i}); } sort(azip.begin(), azip.end()); int atmp = 0; int ans = 0; for(int i = n-1;i >= 0;i--){ pair<int, int> pp = {a[i], i}; pair<int, int> pp2 = {a[i]+1, INT_MIN}; int idx = lower_bound(azip.begin(), azip.end(), pp) - azip.begin(); int start = lower_bound(azip.begin(), azip.end(), pp2) - azip.begin(); auto get = seg.get(start, n); get.first++; if(get.second == 0) get.second = 1; seg.update(idx, get); if(atmp == get.first){ ans += get.second; ans %= MOD; }else if(atmp < get.first){ atmp = get.first; ans = get.second; } } cout << ans << endl; return 0; }