提交时间:2024-03-30 17:18:39
运行 ID: 140698
#include <bits/stdc++.h> using namespace std; const int N = 2e5 + 5; int a[N], x, n, dp[N], maxn; int g[N], cnt; int main() { while (cin >> x) a[++n] = x; g[0] = 2e9; for (int i = 1; i <= n; i++) { if (a[i] <= g[cnt]) g[++cnt] = a[i]; else { int l = 1, r = cnt; while (l < r) { int mid = l + r >> 1; if (g[mid] < a[i]) r = mid; else l = mid + 1; } g[l] = a[i]; } } cout << cnt << " "; cnt = 0; g[0] = -2e9; for (int i = 1; i <= n; i++) { if (a[i] > g[cnt]) g[++cnt] = a[i]; else { int l = 1, r = cnt; while (l < r) { int mid = l + r >> 1; if (g[mid] >= a[i]) r = mid; else l = mid + 1; } g[l] = a[i]; } } cout << cnt << endl; }