結果

問題 No.992 最長増加部分列の数え上げ
ユーザー leaf_1415
提出日時 2020-02-14 22:34:09
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 176 ms / 2,000 ms
コード長 2,609 bytes
コンパイル時間 1,119 ms
コンパイル使用メモリ 76,400 KB
実行使用メモリ 28,760 KB
最終ジャッジ日時 2024-10-06 12:58:15
合計ジャッジ時間 7,479 ms
ジャッジサーバーID
(参考情報)
judge3 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 42
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#define llint long long
#define inf 1e18
#define mod 1000000007
using namespace std;
struct SegTree{
int size;
vector<llint> seg;
SegTree(){}
SegTree(int size){
this->size = size;
seg.resize(1<<(size+1));
}
void init()
{
for(int i = 0; i < (1<<(size+1)); i++) seg[i] = -inf;
}
void update(int i, llint val)
{
i += (1 << size);
seg[i] = val;
while(i > 1){
i /= 2;
seg[i] = max(seg[i*2], seg[i*2+1]);
}
}
llint query(int a, int b, int k, int l, int r)
{
if(b < l || r < a) return -inf;
if(a <= l && r <= b) return seg[k];
llint lval = query(a, b, k*2, l, (l+r)/2);
llint rval = query(a, b, k*2+1, (l+r)/2+1, r);
return max(lval, rval);
}
llint query(int a, int b)
{
return query(a, b, 1, 0, (1<<size)-1);
}
};
llint n;
llint a[200005];
vector<llint> comp;
SegTree seg(18);
llint dp[200005], dp2[200005];
vector<llint> vec[200005], svec[200005];
int main(void)
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) comp.push_back(a[i]);
comp.push_back(-inf);
sort(comp.begin(), comp.end());
comp.erase(unique(comp.begin(), comp.end()), comp.end());
for(int i = 1; i <= n; i++) a[i] = lower_bound(comp.begin(), comp.end(), a[i]) - comp.begin();
seg.init();
seg.update(0, 0);
dp[0] = 0;
for(int i = 1; i <= n; i++){
dp[i] = seg.query(0, a[i]-1) + 1;
seg.update(a[i], dp[i]);
//for(int j = 0; j < 10; j++) cout << seg.query(j, j) << " "; cout << endl;
}
llint lis = seg.query(0, (int)comp.size());
//for(int i = 0; i <= n; i++) cout << dp[i] << " "; cout << endl;
for(int i = 0; i <= n; i++) vec[dp[i]].push_back(i);
svec[0].push_back(1);
dp2[0] = 1;
for(int i = 1; i <= n; i++){
vector<llint> &cvec = vec[dp[i]-1];
llint p = lower_bound(cvec.begin(), cvec.end(), i) - cvec.begin();
//cout << p << endl;
llint ub = p, lb = -1, mid;
while(ub-lb>1){
mid = (ub+lb)/2;
if(a[cvec[mid]] < a[i]) ub = mid;
else lb = mid;
}
//cout << ub << endl;
vector<llint> &csvec = svec[dp[i]-1];
dp2[i] = csvec[p-1];
if(ub > 0) dp2[i] += mod - csvec[ub-1] + mod, dp2[i] %= mod;
if(svec[dp[i]].size() == 0) svec[dp[i]].push_back(dp2[i]);
else svec[dp[i]].push_back((svec[dp[i]].back() + dp2[i]) % mod);
}
//for(int i = 0; i <= n; i++) cout << dp2[i] << " "; cout << endl;
llint ans = 0;
for(int i = 0; i <= n; i++){
if(dp[i] == lis) ans += dp2[i], ans %= mod;
}
cout << ans << endl;
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0