結果

問題 No.992 最長増加部分列の数え上げ
コンテスト
ユーザー RootMirzayanov
提出日時 2026-02-20 19:12:20
言語 C++14
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++14 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 1,106 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,664 ms
コンパイル使用メモリ 184,756 KB
実行使用メモリ 16,452 KB
最終ジャッジ日時 2026-02-20 19:12:27
合計ジャッジ時間 7,165 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 2
other WA * 42
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e5+5,p=1e9+7;
int a[N],n;
pair<int,int> w[N<<2];
pair<int,int> mrg(pair<int,int> x,pair<int,int> y){
	if(x.first==y.first) return make_pair(x.first,(x.second+y.second)%p);
	else if(x.first>y.first) return x;
	else return y;
}
void psh(int u){
	w[u]=mrg(w[u<<1],w[u<<1|1]);
}
void upd(int u,int l,int r,int q,pair<int,int> x){
	if(l==r) w[u]=x;
	else{
		int mid=l+r>>1;
		if(q<=mid) upd(u<<1,l,mid,q,x);
		else upd(u<<1|1,mid+1,r,q,x);
		psh(u);
	}
}
pair<int,int> qry(int u,int l1,int r1,int l2,int r2){
	if(l2>r2) return make_pair(0,1);
	if(l2<=l1&&r1<=r2) return w[u];
	else{
		int mid=l1+r1>>1;
		if(l2>mid) return qry(u<<1|1,mid+1,r1,l2,r2);
		if(r2<=mid) return qry(u<<1,l1,mid,l2,r2);
		return mrg(qry(u<<1,l1,mid,l2,r2),qry(u<<1|1,mid+1,r1,l2,r2));
	}
}
signed main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	for(int i=1;i<=n;i++){
		pair<int,int> res=qry(1,1,n,1,a[i]-1);res.first++,res.second=max(res.second,1LL);
		upd(1,1,n,a[i],res);
	}
	printf("%lld\n",qry(1,1,n,1,n).second);
	return 0;
}
0