-
Notifications
You must be signed in to change notification settings - Fork 4
/
11368.cpp
67 lines (56 loc) · 1.88 KB
/
11368.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <cstring>
using namespace std;
typedef pair<int, int> ii;
int n, t, a, b;
vector<ii> dolls;
vector<int> ans;
/**
* The idea is as follows:
* 1. Sort the input by height asc, then width desc
* 2. Make vector or widths
* 3. For each doll, binary search its width in the array
* 4. If there is a width bigger, simply replace the bigger width with the new width.
* 5. If these is no bigger width, add it to the array.
* 6. Solution is the size of the array.
*
* Sorting is done like so:
* Sort by height first in ascending order. In case of a tie, we want to place the
* smallest width before. This is done to handle cases where there is a tie in heights.
* For instance the case: (2,1) (3,1) (4,1) if the sorting places larger widths before,
* upper bound (in main) will replace the item already placed in the vector.
*
* The idea is that we're leveraging the array farmed with widths and maintaining it in order.
* For each sequence we're maintaining the smallest width of that sequence. This allows
* us to quickly check if we need to create a new sequence for this or not.
*/
struct lt {
inline bool operator() (const ii& p1, const ii& p2) {
return (get<1>(p1) == get<1>(p2)) ? get<0>(p1) < get<0>(p2) : get<1>(p1) > get<1>(p2);
}
};
int main() {
cin >> t;
while (t--) {
dolls.clear(); ans.clear();
cin >> n;
for (int i = 0; i < n; i++) { cin >> a >> b; dolls.push_back(make_pair(a, b)); }
sort(dolls.begin(), dolls.end(), lt());
int used = 0;
for (int i = 0; i < dolls.size(); i++) {
int cur = get<0>(dolls[i]);
int idx = upper_bound(ans.begin(), ans.end(), cur) - ans.begin();
if (idx == ans.size()) {
ans.push_back(cur);
used++;
} else {
ans[idx] = cur;
}
}
cout << used << endl;
}
return 0;
}