Advertisement
Guest User

Untitled

a guest
Sep 23rd, 2019
106
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.68 KB | None | 0 0
  1. //Elements belonging to any LIS
  2. //https://www.spoj.com/problems/SUPPER/
  3. //https://stackoverflow.com/questions/45067878/how-to-check-whether-each-element-is-in-any-longest-increasing-subsequence-of-an
  4. #include <bits/stdc++.h>
  5. #define int long long
  6. using namespace std;
  7.  
  8. int32_t main(){
  9.     ios::sync_with_stdio(false); cin.tie(0);
  10.     int nteste = 10;
  11.     while(nteste--){
  12.         int n; cin >> n;
  13.         vector<int> vet(n), size_lis_ending_in(n), size_lis_starting_at(n), dp;
  14.         for(int &x : vet)
  15.             cin >> x;
  16.         for(int i = 0; i < n; ++i){
  17.             int x = vet[i];
  18.             if(dp.empty() || x > dp.back()){
  19.                 dp.push_back(x);
  20.                 size_lis_ending_in[i] = dp.size();
  21.             }
  22.             else{
  23.                 auto it = lower_bound(dp.begin(), dp.end(), x);
  24.                 *it = x;
  25.                 size_lis_ending_in[i] = it-dp.begin() + 1;
  26.  
  27.             }
  28.         }
  29.         dp.clear();
  30.         for(int i = n-1; i >= 0; --i){
  31.             int x = -vet[i];
  32.             if(dp.empty() || x > dp.back()){
  33.                 dp.push_back(x);
  34.                 size_lis_starting_at[i] = dp.size();
  35.             }
  36.             else{
  37.                 auto it = lower_bound(dp.begin(), dp.end(), x);
  38.                 *it = x;
  39.                 size_lis_starting_at[i] = it-dp.begin() + 1;
  40.  
  41.             }
  42.         }
  43.         set<int> supper;
  44.         for(int i = 0; i < n; ++i){
  45.             if(size_lis_ending_in[i] + size_lis_starting_at[i] - 1 == dp.size())
  46.                 supper.insert(vet[i]);
  47.         }
  48.         cout << supper.size() << '\n';
  49.         for(int x : supper)
  50.             cout << x << ' ';
  51.         cout << '\n';
  52.     }
  53. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement