結果

問題 No.992 最長増加部分列の数え上げ
コンテスト
ユーザー Jungle
提出日時 2026-07-24 12:25:47
言語 C++23(gcc16)
(gcc 16.1.0 + boost 1.90.0)
コンパイル:
g++-16 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 153 ms / 2,000 ms
+ 639µs
コード長 2,624 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,504 ms
コンパイル使用メモリ 230,796 KB
実行使用メモリ 15,488 KB
最終ジャッジ日時 2026-07-24 12:25:55
合計ジャッジ時間 8,020 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 42
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <chrono>
#include <iostream>
#include <map>
#include <random>
#include <utility>
using namespace std;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define Jungle "subseq"
#define MASK(i) (1 << (i))
#define getbit(x, i) (((x) >> (i)) & 1)
#define cntbit(x) __builtin_popcount(x)
#define _(x) ((x) & -(x))
#define MULTEST                                                                                    \
	int numtest;                                                                                   \
	read(numtest);                                                                                 \
	for (; numtest; --numtest)

template <typename t> void mini(t &a, t b)
{
	if (a > b)
		a = b;
}

template <typename t> void maxi(t &a, t b)
{
	if (a < b)
		a = b;
}

const int mod = 1e9 + 7;

int add(const int &x, const int &y)
{
	return (1ll * x + y) % mod;
}

int sub(const int &x, const int &y)
{
	return (1ll * x - y + mod) % mod;
}

int mul(const int &x, const int &y)
{
	return 1ll * x * y % mod;
}

template <typename t> void read(t &x)
{
	cin >> x;
}

const bool is_debug = 1;
const int maxn = 2e5 + 5;

int n, a[maxn];

void init(void)
{
	cin >> n;
	for (int i = 1; i <= n; ++i)
		cin >> a[i];
}

void compress(void)
{
	map<int, int> store;
	for (int i = 1; i <= n; ++i)
		store[a[i]] = 1;
	int cnt = 0;
	for (auto &[v, f] : store)
		f = ++cnt;
	for (int i = 1; i <= n; ++i)
		a[i] = store[a[i]];
}

struct FenwickTree
{
	pair<int, int> bit[maxn];

	void insert(int x, const pair<int, int> &p)
	{
		for (; x <= n; x += _(x))
			if (p.first > bit[x].first)
				bit[x] = p;
			else if (p.first == bit[x].first)
				bit[x].second = add(bit[x].second, p.second);
	}

	pair<int, int> get(int x)
	{
		pair<int, int> ans = {0, 1};
		for (; x > 0; x -= _(x))
			if (bit[x].first > ans.first)
				ans = bit[x];
			else if (ans.first == bit[x].first)
				ans.second = add(ans.second, bit[x].second);
		return ans;
	}
} bit;

void solve(void)
{
	init();
	compress();
	pair<int, int> res = {0, 1};
	for (int i = 1; i <= n; ++i)
	{
		pair<int, int> out = bit.get(a[i] - 1);
		++out.first;
		if (out.first > res.first)
			res = out;
		else if (out.first == res.first)
			res.second = add(out.second, res.second);
		bit.insert(a[i], out);
	}
	cout << res.second << '\n';
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(nullptr);
	cout.tie(nullptr);

	if (fopen(Jungle ".inp", "r"))
	{
		freopen(Jungle ".inp", "r", stdin);
		freopen(Jungle ".out", "w", stdout);
	}

	// MULTEST
	solve();

	// cerr << "\nTime elapsed: " << 1000.0 * clock() / CLOCKS_PER_SEC << "ms\n";

	return 0;
}
0