• API
• FAQ
• Tools
• Trends
• Archive
daily pastebin goal
58%
SHARE
TWEET

# Untitled

a guest Apr 21st, 2017 48 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) {
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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top