http://acm.hust.edu.cn/vjudge/contest/123100#problem/B
#include <iostream> #include <string> #include <cstring> #include <cstdlib> #include <cstdio> #include <cmath> #include <algorithm> #include <stack> #include <queue> #include <cctype> #include <vector> #include <iterator> #include <set> #include <map> #include <sstream> using namespace std; #define mem(a,b) memset(a,b,sizeof(a)) #define pf printf #define sf scanf #define spf sprintf #define pb push_back #define debug printf("! ") #define MAXN 100000 + 10 #define MAX(a,b) a>b?a:b #define blank pf(" ") #define LL long long #define ALL(x) x.begin(),x.end() #define INS(x) inserter(x,x.begin()) #define pqueue priority_queue #define INF 0x3f3f3f3f int n,m; struct node { int h,w; }a[200005],b[200005]; bool cmp(node x,node y) { return x.h < y.h; } multiset<int> mt; multiset<int>::iterator it; int main() { int i,j; int t; sf("%d",&t); while(t--) { sf("%d",&n); for(i=1;i<=n;i++) { sf("%d%d",&a[i].h,&a[i].w); } for(i=1;i<=n;i++) { sf("%d%d",&b[i].h,&b[i].w); } sort(a+1,a+n+1,cmp); sort(b+1,b+n+1,cmp); mt.clear(); int cnt=0; for(i=1,j=1;i<=n;i++) { while(j<=n && a[i].h>=b[j].h) { mt.insert(b[j].w); j++; } if(mt.empty()) continue; it = mt.upper_bound(a[i].w); if(it!=mt.begin()) it--; if((*it) <= a[i].w) { cnt++; mt.erase(it); } } pf("%d ",cnt); } return 0; }