結果
問題 | No.992 最長増加部分列の数え上げ |
ユーザー | fine |
提出日時 | 2020-02-15 00:12:28 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 268 ms / 2,000 ms |
コード長 | 5,259 bytes |
コンパイル時間 | 2,138 ms |
コンパイル使用メモリ | 190,000 KB |
実行使用メモリ | 39,280 KB |
最終ジャッジ日時 | 2024-10-06 13:32:42 |
合計ジャッジ時間 | 11,278 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,820 KB |
testcase_01 | AC | 2 ms
6,816 KB |
testcase_02 | AC | 2 ms
6,816 KB |
testcase_03 | AC | 2 ms
6,816 KB |
testcase_04 | AC | 86 ms
11,392 KB |
testcase_05 | AC | 62 ms
9,344 KB |
testcase_06 | AC | 106 ms
13,184 KB |
testcase_07 | AC | 77 ms
10,496 KB |
testcase_08 | AC | 40 ms
7,168 KB |
testcase_09 | AC | 79 ms
10,752 KB |
testcase_10 | AC | 109 ms
13,056 KB |
testcase_11 | AC | 135 ms
15,744 KB |
testcase_12 | AC | 26 ms
6,816 KB |
testcase_13 | AC | 73 ms
10,240 KB |
testcase_14 | AC | 74 ms
10,240 KB |
testcase_15 | AC | 27 ms
6,816 KB |
testcase_16 | AC | 206 ms
22,144 KB |
testcase_17 | AC | 40 ms
7,168 KB |
testcase_18 | AC | 72 ms
10,112 KB |
testcase_19 | AC | 134 ms
15,488 KB |
testcase_20 | AC | 231 ms
24,192 KB |
testcase_21 | AC | 231 ms
24,064 KB |
testcase_22 | AC | 229 ms
24,192 KB |
testcase_23 | AC | 229 ms
24,064 KB |
testcase_24 | AC | 231 ms
24,192 KB |
testcase_25 | AC | 229 ms
24,192 KB |
testcase_26 | AC | 229 ms
24,192 KB |
testcase_27 | AC | 231 ms
24,064 KB |
testcase_28 | AC | 234 ms
24,192 KB |
testcase_29 | AC | 228 ms
24,064 KB |
testcase_30 | AC | 239 ms
39,152 KB |
testcase_31 | AC | 233 ms
39,160 KB |
testcase_32 | AC | 247 ms
39,192 KB |
testcase_33 | AC | 227 ms
39,176 KB |
testcase_34 | AC | 236 ms
39,276 KB |
testcase_35 | AC | 239 ms
39,144 KB |
testcase_36 | AC | 240 ms
39,160 KB |
testcase_37 | AC | 240 ms
39,084 KB |
testcase_38 | AC | 239 ms
39,208 KB |
testcase_39 | AC | 234 ms
39,280 KB |
testcase_40 | AC | 267 ms
33,852 KB |
testcase_41 | AC | 268 ms
33,940 KB |
testcase_42 | AC | 268 ms
33,944 KB |
testcase_43 | AC | 267 ms
33,892 KB |
testcase_44 | AC | 261 ms
33,780 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; const ll MOD = 1000000007; ll modpow(ll x, ll n, ll mod = MOD) { ll res = 1; while (n > 0) { if (n & 1) res = res * x % mod; x = x * x % mod; n >>= 1; } return res; } const ll INF = 1e15; //引数unzipには圧縮前のvectorを入れる int compress(vector<ll>& unzip, map<ll, int>& zip) { sort(unzip.begin(), unzip.end()); unzip.erase(unique(unzip.begin(), unzip.end()), unzip.end()); for (int i = 0; i < unzip.size(); i++) { zip[unzip[i]] = i; } return unzip.size(); } template <class Monoid> struct SegmentTree { using T = typename Monoid::T; int n; vector<T> data; SegmentTree() {} SegmentTree(int size, T initial_value = Monoid::unit()) { n = 1; while (n < size) n <<= 1; data.assign(2 * n - 1, initial_value); if (initial_value != Monoid::unit()) { for (int i = n - 2; i >= 0; i--) data[i] = Monoid::merge(data[i * 2 + 1], data[i * 2 + 2]); } } SegmentTree(const vector<T>& v) { int size = v.size(); n = 1; while (n < size) n <<= 1; data.assign(2 * n - 1, Monoid::unit()); for (int i = 0; i < size; i++) data[i + n - 1] = v[i]; for (int i = n - 2; i >= 0; i--) data[i] = Monoid::merge(data[i * 2 + 1], data[i * 2 + 2]); } T getLeaf(int k) { return data[k + n - 1]; } void update(int k, T x) { k += n - 1; //葉の節点 Monoid::update(data[k], x); while (k > 0) { k = (k - 1) / 2; data[k] = Monoid::merge(data[k * 2 + 1], data[k * 2 + 2]); } } //区間[a, b)に対するクエリに答える //k:節点番号, [l, r):節点に対応する区間 T query(int a, int b, int k, int l, int r) { //[a, b)と[l, r)が交差しない場合 if (r <= a || b <= l) return Monoid::unit(); //[a, b)が[l, r)を含む場合、節点の値 if (a <= l && r <= b) return data[k]; else { //二つの子をマージ T vl = query(a, b, k * 2 + 1, l, (l + r) / 2); T vr = query(a, b, k * 2 + 2, (l + r) / 2, r); return Monoid::merge(vl, vr); } } //外から呼ぶ用 T query(int a, int b) { return query(a, b, 0, 0, n); } //非再帰版: バグってるかもしれないので定数倍高速化する時以外使わないで //区間[a, b)に対するクエリに答える T query_fast(int a, int b) { T vl = Monoid::unit(), vr = Monoid::unit(); for (int l = a + n, r = b + n; l != r; l >>= 1, r >>= 1) { if (l & 1) vl = Monoid::merge(vl, data[l++ - 1]); if (r & 1) vr = Monoid::merge(data[--r - 1], vr); } return Monoid::merge(vl, vr); } }; // 以下、Monoidの例 template <class U = ll> struct RangeMin { using T = U; static T merge(T x, T y) { return min(x, y); } static void update(T& target, T x) { target = x; } static constexpr T unit() { return numeric_limits<T>::max(); } }; template <class U = ll> struct RangeSum { using T = U; static T merge(T x, T y) { return (x + y) % MOD; } static void update(T& target, T x) { (target += x) %= MOD; } static constexpr T unit() { return T(0); } }; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int n; cin >> n; vector<ll> a(n); for (int i = 0; i < n; ++i) { cin >> a[i]; } vector<ll> zip = a; map<ll, int> unzip; int sz = compress(zip, unzip); vector<ll> dp(n + 1, INF); vector<int> num(n); for (int i = 0; i < n; ++i) { int idx = lower_bound(dp.begin(), dp.end(), a[i]) - dp.begin(); num[i] = idx; dp[idx] = a[i]; } int max_len = lower_bound(dp.begin(), dp.end(), INF) - dp.begin(); // cerr << max_len << endl; vector< vector<int> > ids(max_len); for (int i = 0; i < n; ++i) { ids[num[i]].push_back(i); } vector<ll> dp2(n, 0); for (int i : ids[0]) { dp2[i] = 1; } for (int i = 0; i < max_len - 1; ++i) { vector<int>& cur = ids[i]; vector<int>& nex = ids[i + 1]; vector<ll> v; for (int j : cur) v.push_back(a[j]); for (int j : nex) v.push_back(a[j]); map<ll, int> unzip; int sz = compress(v, unzip); SegmentTree< RangeSum<> > tmp(sz); for (int ii = 0, jj = 0; ;) { if (jj == nex.size()) break; if (ii == cur.size()) { dp2[nex[jj]] = tmp.query_fast(0, unzip[a[nex[jj]]]); ++jj; } else { if (cur[ii] < nex[jj]) { int idx = unzip[a[cur[ii]]]; tmp.update(idx, dp2[cur[ii]]); ++ii; } else { dp2[nex[jj]] = tmp.query_fast(0, unzip[a[nex[jj]]]); ++jj; } } } } ll ans = 0; for (int i = 0; i < n; ++i) { //cerr << dp2[i] << endl; if (num[i] + 1 == max_len) (ans += dp2[i]) %= MOD; } cout << ans << "\n"; return 0; }