結果
問題 |
No.992 最長増加部分列の数え上げ
|
ユーザー |
![]() |
提出日時 | 2020-03-19 18:34:10 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 206 ms / 2,000 ms |
コード長 | 1,047 bytes |
コンパイル時間 | 891 ms |
コンパイル使用メモリ | 75,204 KB |
最終ジャッジ日時 | 2025-01-09 07:57:14 |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 42 |
ソースコード
#include <iostream> #include <algorithm> using namespace std; typedef long long ll; typedef pair<ll,ll> pll; ll n,mod = 1000000007; pll seg[400010],INF = {0,1}; pll cal(pll p, pll q){ if(p.first>q.first) return p; if(p.first<q.first) return q; pll r = {p.first,(p.second + q.second)%mod}; return r; } void init(int n){ for(int i=n - 1;i>0;i--){ seg[i] = cal(seg[i<<1],seg[i<<1|1]); } } void update(pll val,int p){ for(seg[p += n] = val;p>1;p>>=1){ seg[p>>1] = cal(seg[p],seg[p^1]); } } pll query(int l,int r){ pll res = INF; for(l += n,r += n; l<r;l>>=1,r>>=1){ if(l&1) res = cal(res,seg[l++]); if(r&1) res = cal(res,seg[--r]); } return res; } pll a[200010]; int main(){ int i; cin >> n; for(i=0;i<n;i++){ ll b; cin >> b; a[i] = {b,-i}; } sort(a,a + n); for(i=0;i<n;i++){ int ind = -a[i].second; pll p = query(0,ind); p.first++; update(p,ind); } cout << query(0,n).second << endl; }