結果

問題 No.992 最長増加部分列の数え上げ
ユーザー heno_code
提出日時 2020-02-15 03:16:52
言語 C++14
(gcc 9.2.0)
結果
AC  
実行時間 392 ms
コード長 2,229 Byte
コンパイル時間 1,496 ms
使用メモリ 22,180 KB
最終ジャッジ日時 2020-02-15 03:17:04

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
1_sample1.txt AC 0 ms
3,276 KB
2_sample2.txt AC 4 ms
3,288 KB
3_sample3.txt AC 0 ms
3,344 KB
4.txt AC 4 ms
3,376 KB
5.txt AC 108 ms
11,324 KB
6.txt AC 80 ms
7,960 KB
7.txt AC 136 ms
12,276 KB
8.txt AC 96 ms
10,752 KB
9.txt AC 44 ms
6,796 KB
10.txt AC 96 ms
10,864 KB
11.txt AC 136 ms
12,212 KB
12.txt AC 184 ms
13,588 KB
13.txt AC 24 ms
5,292 KB
14.txt AC 88 ms
10,480 KB
15.txt AC 96 ms
10,712 KB
16.txt AC 28 ms
5,156 KB
17.txt AC 332 ms
20,992 KB
18.txt AC 48 ms
6,884 KB
19.txt AC 88 ms
10,552 KB
20.txt AC 188 ms
13,344 KB
21.txt AC 332 ms
22,140 KB
22.txt AC 356 ms
22,088 KB
23.txt AC 352 ms
22,068 KB
24.txt AC 340 ms
22,180 KB
25.txt AC 372 ms
22,168 KB
26.txt AC 384 ms
22,080 KB
27.txt AC 372 ms
22,100 KB
28.txt AC 392 ms
22,076 KB
29.txt AC 352 ms
22,048 KB
30.txt AC 360 ms
22,156 KB
31.txt AC 188 ms
21,064 KB
32.txt AC 188 ms
21,108 KB
33.txt AC 188 ms
21,048 KB
34.txt AC 192 ms
21,088 KB
35.txt AC 188 ms
21,092 KB
36.txt AC 184 ms
21,032 KB
37.txt AC 184 ms
21,108 KB
38.txt AC 188 ms
21,084 KB
39.txt AC 184 ms
21,016 KB
40.txt AC 184 ms
21,044 KB
41.txt AC 188 ms
21,064 KB
42.txt AC 192 ms
21,024 KB
43.txt AC 188 ms
21,012 KB
44.txt AC 196 ms
21,032 KB
45.txt AC 196 ms
20,992 KB
テストケース一括ダウンロード

ソースコード

diff #
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<utility>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<cassert>
#include<random>
#include<unordered_map>
#include<numeric>
using namespace std;
using ll = long long;
const ll mod = 1000000007;
const ll INF = (1e+18) + 7;
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define all(x) (x).begin(),(x).end()
#define stop char nyaa;cin>>nyaa;

using P = pair<int, int>;
using LP = pair<ll, ll>;

struct SegT {
private:
	int sz; vector<LP> node;
	const LP init_c = { 0,0 };
public:
	SegT(int n) {
		sz = 1;
		while (sz < n)sz *= 2;
		node.resize(2 * sz - 1, init_c);
	}
	LP f(LP a, LP b) {
		if (a.first < b.first)return b;
		if (a.first > b.first)return a;
		ll res = a.second + b.second;
		if (res >= mod)res -= mod;
		return { a.first,res };
	}
	void update(int k, LP a) {
		k += sz - 1;
		if (node[k].first == a.first) {
			node[k].second += a.second;
			if (node[k].second >= mod)node[k].second -= mod;
		}
		else if (node[k].first<a.first)node[k] = a;
		while (k > 0) {
			k = (k - 1) / 2;
			node[k] = f(node[k * 2 + 1], node[k * 2 + 2]);
		}
	}
	LP query(int a, int b, int k = 0, int l = 0, int r = -1) {
		if (r < 0)r = sz;
		if (r <= a || b <= l)return init_c;
		else if (a <= l && r <= b)return node[k];
		else {
			LP vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
			LP vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
			return f(vl, vr);
		}
	}
};

void solve() {
	int n; cin >> n;
	vector<int> a(n);
	rep(i, n) {
		cin >> a[i];
	}
	vector<int> x;
	rep(i, n)x.push_back(a[i]);
	x.push_back(-mod);
	sort(all(x));
	x.erase(unique(all(x)), x.end());
	map<int, int> mp;
	rep(i, x.size())mp[x[i]] = i;
	rep(i, n)a[i] = mp[a[i]];

	SegT st(x.size());
	st.update(0,{ 0,1 });
	rep(i, n) {
		LP p = st.query(0, a[i]);
		p.first++;
		st.update(a[i], p);
	}
	LP ans = st.query(0, x.size());
	cout << ans.second << endl;

}
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	//int t; cin >> t;rep(i,t) solve();
	solve();
	stop
		return 0;
}
0