結果

問題 No.992 最長増加部分列の数え上げ
ユーザー chocorusk
提出日時 2020-02-15 04:56:21
言語 C++14
(gcc 9.2.0)
結果
AC  
実行時間 300 ms
コード長 2,144 Byte
コンパイル時間 1,064 ms
使用メモリ 15,868 KB
最終ジャッジ日時 2020-02-15 04:56:34

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
1_sample1.txt AC 4 ms
6,352 KB
2_sample2.txt AC 4 ms
6,292 KB
3_sample3.txt AC 4 ms
6,336 KB
4.txt AC 0 ms
6,400 KB
5.txt AC 108 ms
10,708 KB
6.txt AC 76 ms
8,404 KB
7.txt AC 128 ms
10,848 KB
8.txt AC 92 ms
10,576 KB
9.txt AC 52 ms
8,420 KB
10.txt AC 96 ms
10,852 KB
11.txt AC 128 ms
10,704 KB
12.txt AC 164 ms
11,032 KB
13.txt AC 32 ms
7,072 KB
14.txt AC 88 ms
10,516 KB
15.txt AC 96 ms
10,520 KB
16.txt AC 36 ms
7,084 KB
17.txt AC 260 ms
15,516 KB
18.txt AC 48 ms
8,392 KB
19.txt AC 88 ms
10,576 KB
20.txt AC 164 ms
11,020 KB
21.txt AC 280 ms
15,800 KB
22.txt AC 292 ms
15,868 KB
23.txt AC 288 ms
15,788 KB
24.txt AC 292 ms
15,792 KB
25.txt AC 288 ms
15,864 KB
26.txt AC 288 ms
15,732 KB
27.txt AC 296 ms
15,788 KB
28.txt AC 300 ms
15,860 KB
29.txt AC 300 ms
15,772 KB
30.txt AC 300 ms
15,784 KB
31.txt AC 252 ms
15,856 KB
32.txt AC 244 ms
15,732 KB
33.txt AC 244 ms
15,672 KB
34.txt AC 248 ms
15,800 KB
35.txt AC 240 ms
15,728 KB
36.txt AC 248 ms
15,676 KB
37.txt AC 244 ms
15,796 KB
38.txt AC 244 ms
15,856 KB
39.txt AC 248 ms
15,800 KB
40.txt AC 244 ms
15,784 KB
41.txt AC 232 ms
15,808 KB
42.txt AC 228 ms
15,780 KB
43.txt AC 232 ms
15,856 KB
44.txt AC 236 ms
15,780 KB
45.txt AC 232 ms
15,776 KB
テストケース一括ダウンロード

ソースコード

diff #
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, ll> P;
const ll MOD=1e9+7;
template<typename Monoid>
struct SegmentTree{
	using F=function<Monoid(Monoid, Monoid)>;
	int sz;
	vector<Monoid> seg;
	const F f;
	const Monoid e;

	SegmentTree(int n, const F f, const Monoid &e): f(f), e(e){
		sz=1;
		while(sz<n) sz<<=1;
		seg.resize(2*sz, e);
	}

	SegmentTree(int n, const F f, const Monoid &e, vector<Monoid> v): f(f), e(e){
		sz=1;
		while(sz<n) sz<<=1;
		seg.resize(2*sz, e);
		for(int i=0; i<n; i++) seg[i+sz]=v[i];
		for(int i=sz-1; i>=1; i--){
			seg[i]=f(seg[2*i], seg[2*i+1]);
		}
	}

	void update(int k, const Monoid &x){
		k+=sz;
		seg[k]=x;
		while(k>1){
			k>>=1;
			seg[k]=f(seg[2*k], seg[2*k+1]);
		}
	}

	Monoid query(int a, int b){
		a+=sz, b+=sz;
		Monoid ret=e;
		for(;a<b; a>>=1, b>>=1){
			if(b&1) ret=f(ret, seg[--b]);
			if(a&1) ret=f(ret, seg[a++]);
		}
		return ret;
	}

	Monoid operator[](const int &k) const{
		return seg[k+sz];
	}
};
int main()
{
	int n; cin>>n;
	int a[200020];
	vector<int> va(n);
	for(int i=0; i<n; i++){
		cin>>a[i];
		va[i]=a[i];
	}
	sort(va.begin(), va.end());
	va.erase(unique(va.begin(), va.end()), va.end());
	int m=va.size()+1;
	for(int i=0; i<n; i++) a[i]=lower_bound(va.begin(), va.end(), a[i])-va.begin()+1;
	P dp[200020];
	dp[0]=P(0, 1);
	auto f=[](P a, P b){
		if(a.first!=b.first) return max(a, b);
		else return P(a.first, (a.second+b.second)%MOD);
	};
	SegmentTree<P> seg(m, f, P(-1, 0));
	seg.update(0, dp[0]);
	for(int i=0; i<n; i++){
		P p=seg.query(0, a[i]);
		dp[i+1]=P(p.first+1, p.second);
		seg.update(a[i], f(seg[a[i]], dp[i+1]));
	}
	P ans=seg.query(0, m);
	cout<<ans.second<<endl;
	return 0;
}
0