SHARE
TWEET

Untitled

a guest Apr 21st, 2017 47 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. int main()
  6. {
  7.     int tests; // number of test cases
  8.     cin >> tests;
  9.     int count = 0; // counter for test cases
  10.  
  11.     long* sol = new long[tests]; // array with solutions
  12.  
  13.     while (count < tests) {
  14.         // load array
  15.         long n;
  16.         cin >> n; // size of the array
  17.         if (n == 1) {
  18.             sol[count] = 0;
  19.             long k;
  20.             cin >> k;
  21.  
  22.             //cout << count << " " << sol [count] << endl;
  23.             count++;
  24.         } else {
  25.             long* a = new long[n];
  26.  
  27.             long last = -1; // last in the remaining sequence
  28.             long maxInSubsequence = 0;
  29.             long lastIndex = 0;
  30.  
  31.             // longest subsequence
  32.             long* T = new long[n]; // stores indexes of elements from a[]; the index of the smallest last element of some length
  33.             T[0] = 0;
  34.             long temp = 0;
  35.             cin >> a[0];
  36.  
  37.             while (temp < n) {
  38.                 long jump = 0;
  39.  
  40.                 if (a[temp] > last) {
  41.                     //cout << "ostace na kraju: " << a[temp] << endl;
  42.                     last = a[temp];
  43.                     lastIndex = temp + 1;
  44.                     temp++;
  45.                 } else {
  46.                     long i = lastIndex + 1;
  47.                     long length = 0;
  48.                     T[jump] = lastIndex;
  49.                     cin >> a[i];
  50.                     while (i < n && a[i] < last) {
  51.                         //cout << "processing " << a[i] << endl;
  52.                         if (a[i] < a[T[0 + jump]]) { //a[i] is smaller than the smallest element in the smallest subsequence
  53.                             T[0 + jump] = i;
  54.                         } else if (a[i] > a[T[length + jump]]) { //a[i] is bigger than the last element in the largest subsequence,
  55.                             length++;                    //so make a bigger subsequence with a[i] on head
  56.                             T[length + jump] = i;
  57.                             //cout << "adding: " << a[i] << endl;
  58.                             //cout << "length " << length << endl;
  59.                         } else { // a[i] is somewhere in between, binary search for the ceiling for a[i]
  60.                             long start = 0;
  61.                             long end = length;
  62.                             long upperMiddle = length;
  63.                             long middle;
  64.                             long ceiling;
  65.                             bool found = false;
  66.                             while (start <= end && !found) {
  67.                                 middle = (start + end) / 2;
  68.                                 if (middle < upperMiddle && a[T[middle + jump]] <= a[i] && a[T[middle + 1 + jump]] >= a[i]) { // comparing values from a[] with indexes from T
  69.                                     ceiling = middle + 1;// the ceiling = the smallest value bigger than a[i]
  70.                                     found = true;
  71.                                 } else if (a[i] > a[T[middle + jump]]){ // if it's bigger go right, search (middle + 1, end)
  72.                                     start = middle + 1;
  73.                                 } else { // else if it's smaller go left, search (start, middle - 1)
  74.                                     end = middle - 1;
  75.                                 }
  76.                             }
  77.                         T[ceiling + jump] = i;//replace the ceiling with i
  78.                         }
  79.                         i++;
  80.                         if (i < n)
  81.                             cin  >> a[i];
  82.                     }
  83.  
  84.                     jump += length + 1;
  85.                     if (maxInSubsequence < length + 1) maxInSubsequence = length + 1;
  86.                     temp = i + 1;
  87.                 }
  88.                 if (temp < n)
  89.                     cin >> a[temp];
  90.             }
  91.  
  92.             /*for (int i = 0; i < n; i++) {
  93.                 cout << a[i] << endl;
  94.             }*/
  95.             sol[count] = maxInSubsequence;
  96.             //cout << count << " " << sol [count] << endl;
  97.             count++;
  98.         }
  99.     }
  100.     for (int i = 0; i < count; i++) {
  101.         cout << sol[i] << endl;
  102.     }
  103.     return 0;
  104. }
RAW Paste Data
Top