MDOLLS - Nested Dolls
Tác giả: khuc_tuan
Ngôn ngữ: C++
#include <iostream>
#include <set>
using namespace std;
int n;
pair<int,int> a[20200];
int main() {
int st;
scanf("%d", &st);
for(int t=0;t<st;++t) {
scanf("%d", &n);
for(int i=0;i<n;++i)
scanf("%d%d", &a[i].first, &a[i].second);
sort( a, a+n);
multiset<int> se;
for(int i=0;i<n;++i) if(i==0 || a[i].first != a[i-1].first) {
for(int j=i;j<n && a[j].first==a[i].first;++j) {
multiset<int>::iterator p = se.lower_bound(a[j].second);
if(p!=se.begin()) {
--p;
se.erase(p);
}
}
for(int j=i;j<n && a[j].first==a[i].first;++j) se.insert(a[j].second);
}
cout << se.size() << endl;
}
return 0;
}