fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define Sonic ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  4. #define tests(t) int t; cin >> t; while(t--)
  5. #define F first
  6. #define S second
  7. #define pb push_back
  8. #define eb emplace_back
  9. #define ln cout<<endl;
  10. #define sz(x) int((x).size())
  11. #define all(x) (x).begin(), (x).end()
  12. #define rall(x) (x).rbegin(), (x).rend()
  13. #define read(x) for(auto &el : x) cin >> el;
  14. #define reads(s, n) for(int i = 0, x; i < n; ++i) {cin >> x; s.insert(x);}
  15. #define forn(i,n) for(int i=0; i < int(n); ++i)
  16. #define forsn(i, s, n) for (int i = s; i < n; ++i)
  17. #define dforn(i, n) for (int i = n - 1; i >= 0; --i)
  18. #define DBG(x) cout << #x << " = " << x << endl;
  19. #define print(x) for(auto &el : x) {cout << el << " ";} cout<<endl;
  20. #define lw(c, x) int(lower_bound((c).begin(), (c).end(), (x)) - (c).begin())
  21. #define up(c, x) int(upper_bound((c).begin(), (c).end(), (x)) - (c).begin())
  22. #define sino(b) cout<<(b ? "YES\n":"NO\n");
  23. #define syso(x) cout<< (x) <<endl;
  24. #define kill(x) {cout<< (x) <<endl; return;}
  25. typedef long long ll;
  26. typedef long double ld;
  27. typedef vector<int> vi;
  28. typedef vector<ll> vll;
  29. typedef pair<int,int> pii;
  30. typedef pair<int,pii> piii;
  31. typedef pair<ll,ll> pll;
  32. ll gcd(ll a, ll b){while(b){a%=b; swap(a,b);} return a;} ll lcm(ll a,ll b){return a*b/gcd(a,b);}
  33. int lg2(const int &x) { return 31-__builtin_clz(x);} // int lg2(const ll &x) {return 63-__builtin_clzll(x);}
  34. // Para leer e imprimir .txt
  35. // freopen("input.txt", "r", stdin);
  36. // freopen("output.txt", "w", stdout);
  37.  
  38.  
  39. const int MAX = 1e5+5;
  40. // int A[MAX];
  41. int dp[MAX];
  42. vector<int> LIS; // PARA Lis_opt
  43. int n;
  44.  
  45. int lis_opt(vector<int> &A) {
  46.     LIS.clear();
  47.     for (int i = 0; i < n; i++) {
  48.         auto id = lower_bound(LIS.begin(), LIS.end(), A[i]);
  49.         if (id == LIS.end()) {
  50.             LIS.pb(A[i]);
  51.             dp[i] = LIS.size();
  52.         }
  53.         else {
  54.             int idx = id - LIS.begin();
  55.             LIS[idx] = A[i];
  56.             dp[i] = idx + 1;
  57.         }
  58.     }
  59.     return LIS.size();
  60. }
  61.  
  62. stack<int> rb;
  63. void build(vector<int> &A) {
  64.     int k = LIS.size();
  65.     int cur = 1e9;
  66.     for (int i = n - 1; i >= 0, k; i--) {
  67.         if (A[i] < cur && k == dp[i]) {
  68.             cur = A[i];
  69.             rb.push(A[i]);
  70.             k--;
  71.         }
  72.     }
  73. }
  74.  
  75. void solve(){
  76.     int x;
  77.     vi a;
  78.     while (cin>>x) a.pb(x);
  79.     n = sz(a);
  80.     lis_opt(a);
  81.     build(a);
  82.     syso(sz(rb))
  83.     syso('-')
  84.     while (!rb.empty()){syso(rb.top())rb.pop();}
  85.     cout << endl;
  86. }
  87.  
  88. int main(){
  89.     Sonic
  90.     // tests(t)
  91.         solve();
  92.     return 0;
  93. }
  94. //"Quiero picha" - Sebastian Nieto 2026
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
5
6
7
8
9
1
2
3
4
stdout
copy 
5
-
5
6
7
8
9
https://ideone.com/DiXPSU
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!