結果

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

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
1_sample1.txt AC 0 ms
3,316 KB
2_sample2.txt AC 4 ms
3,300 KB
3_sample3.txt AC 0 ms
3,296 KB
4.txt AC 0 ms
3,244 KB
5.txt AC 100 ms
11,264 KB
6.txt AC 68 ms
7,896 KB
7.txt AC 136 ms
12,248 KB
8.txt AC 92 ms
10,716 KB
9.txt AC 44 ms
6,852 KB
10.txt AC 96 ms
10,796 KB
11.txt AC 128 ms
12,156 KB
12.txt AC 176 ms
13,640 KB
13.txt AC 24 ms
5,196 KB
14.txt AC 84 ms
10,528 KB
15.txt AC 80 ms
10,788 KB
16.txt AC 28 ms
5,236 KB
17.txt AC 292 ms
21,020 KB
18.txt AC 44 ms
6,768 KB
19.txt AC 80 ms
10,444 KB
20.txt AC 176 ms
13,268 KB
21.txt AC 328 ms
22,128 KB
22.txt AC 340 ms
22,048 KB
23.txt AC 336 ms
22,052 KB
24.txt AC 332 ms
22,128 KB
25.txt AC 328 ms
22,040 KB
26.txt AC 320 ms
22,056 KB
27.txt AC 324 ms
22,152 KB
28.txt AC 320 ms
22,124 KB
29.txt AC 328 ms
22,120 KB
30.txt AC 324 ms
22,116 KB
31.txt AC 180 ms
21,044 KB
32.txt AC 176 ms
21,000 KB
33.txt AC 184 ms
21,032 KB
34.txt AC 184 ms
21,072 KB
35.txt AC 180 ms
20,984 KB
36.txt AC 184 ms
20,988 KB
37.txt AC 172 ms
21,092 KB
38.txt AC 176 ms
21,068 KB
39.txt AC 176 ms
21,016 KB
40.txt AC 176 ms
21,080 KB
41.txt WA -
42.txt WA -
43.txt WA -
44.txt WA -
45.txt WA -
テストケース一括ダウンロード

ソースコード

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;
		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