Cod sursa(job #2922509)

Utilizator raresgherasaRares Gherasa raresgherasa Data 8 septembrie 2022 18:55:28
Problema Subsir crescator maximal Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin ("scmax.in");
ofstream fout ("scmax.out");

const int NM = 2e5 + 5;

int a[NM], d[NM], p[NM], n, k;

int main(){
  fin >> n;
  for (int i = 1; i <= n; i++){
    fin >> a[i];
  }
  d[++k] = a[1];
  p[1] = 1;
  for (int i = 2; i <= n; i++){
    if (a[i] > d[k]){
      d[++k] = a[i];
      p[i] = k;
    }
    else{
      int l = 1, r = k, ans = k;
      while (l <= r){
        int mid = (l + r) / 2;
        if (d[mid] > a[i]){
          r = mid - 1;
          ans = mid;
        }
        else{
          l = mid + 1;
        }
      }
      d[ans] = a[i];
      p[i] = ans;
    }
  }
  set<int>s;
  int j = n;
  for (int i = k; i >= 1; i--){
    while (p[j] != i){
      j -= 1;
    }
    s.insert(a[j]);
  }
  fout << (int)s.size() << '\n';
  for (int x : s){
    fout << x << " ";
  }
}