WA#1 求debug
查看原帖
WA#1 求debug
743373
Vitamin_B楼主2024/5/23 14:43
# pragma GCC optimize("Ofast,no-stack-protector")

# pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

# include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef pair <int, int> pii;

int n, a[100005], dp[100005], tr[100005], maxx, ans[100005], m, r[100005];

void insert (int x, int y) {

	while (x <= n)
		tr[x] = max (tr[x], y), x += x & -x;

	return ;

}

int find (int x) {

	int maxx = 0;

	while (x)
		maxx = max (tr[x], maxx), x ^= x & -x;

	return maxx;

}

int main () {

	ios::sync_with_stdio (0);

	cin.tie (0);

	cout.tie (0);

	for (int i = 0; i < 10; ++ i) {

		cin >> n;

		fill (tr + 1, tr + 1 + n, 0);

		fill (r + 1, r + 1 + n, 0);

		for (int i = 1; i <= n; ++ i) {

			cin >> a[i];

			maxx = max (maxx, dp[i] = find (a[i] - 1) + 1);

			insert (a[i], dp[i]);

		}

		m = 0;

		for (int i = n; i; -- i) {

			if (dp[i] >= maxx || r[dp[i] + 1] > a[i])
				ans[++ m] = a[i];

			r[dp[i]] = max (r[dp[i]], a[i]);

		}

		sort (ans + 1, ans + 1 + m);

		cout << m << '\n';

		for (int i = 1; i <= m; ++ i)
			cout << ans[i] << ' ';

		cout << '\n';
//		return 0;
	}

	return 0;

}
2024/5/23 14:43
加载中...