ccbeginner

UVa Q481

Feb 6th, 2020
97
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //UVa Q481
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. struct pir{
  6.     int val, idx;
  7.     bool operator<(const pir &x)const{return val < x.val;}
  8. };
  9. vector<pir> arr, v;
  10. vector<int> track, ans;
  11.  
  12. int main(){
  13.     int x;
  14.     while(cin >> x){
  15.         pir in = {.val = x, .idx = arr.size()};
  16.         arr.emplace_back(in);
  17.     }
  18.     track.resize(arr.size(), -1);
  19.     v.emplace_back(arr[0]);
  20.     for(int i = 1; i < arr.size(); ++i){
  21.         if(arr[i].val > v.back().val){
  22.             track[i] = v.back().idx;
  23.             v.emplace_back(arr[i]);
  24.         }else{
  25.             auto it = lower_bound(v.begin(), v.end(), arr[i]);
  26.             (*it) = arr[i];
  27.             if(it != v.begin()){
  28.                 --it;
  29.                 track[i] = (*it).idx;
  30.                 ++it;
  31.             }
  32.         }
  33.     }
  34.     cout << v.size() << "\n-\n";
  35.     x = v.back().idx;
  36.     while(~x){
  37.         ans.emplace_back(arr[x].val);
  38.         x = track[x];
  39.     }
  40.     for(int i = ans.size()-1; i >= 0; --i)cout << ans[i] << '\n';
  41.     return 0;
  42. }
RAW Paste Data