Leaving Auction
题目链接：http://codeforces.com/contest/749/problem/D
二分
本来以为是哪种神奇的数据结构，没想到sort+lower_bonud就解决了，妙。
这道题的精髓在于将每个人出价的最大值记录下来，最后竞拍到的一定为没有leave的人中出价最高的那个人（因为It's guaranteed that the sum of k over all question won't exceed 200 000. 所以这个操作的总复杂度不会超过200 000）。而这个人的最低出价，只需要比第二个人的最高出价高即可，此操作可以用二分。//最后不得不说scanf和cin在没有关同步之前，差别真的很大...
代码如下：
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <set>
#define pb(x) push_back(x)
#define N 200005
using namespace std;
int n,q,k,t,biggest[N],person[N];
vector<int>man[N];
bool cmp(int a,int b){
return biggest[a]<biggest[b];
}
int main(void){
scanf("%d",&n);
for(int i=;i<=n;++i){
int a,b;
scanf("%d%d",&a,&b);
man[a].pb(b);
biggest[a]=b;
person[i]=i;
}
sort(person+,person++n,cmp);
scanf("%d",&q);
while(q--){
set<int>leave;
scanf("%d",&k);
for(int i=;i<k;++i){
scanf("%d",&t);
leave.insert(t);
}
int temp[],num=;
temp[]=temp[]=;
for(int i=n;i>=;--i){
if(leave.count(person[i]))continue;
temp[num++]=person[i];
if(num==)break;
}
if(man[temp[]].size()==){
printf("0 0\n");
continue;
}
if(num==){
int it=*lower_bound(man[temp[]].begin(),man[temp[]].end(),biggest[temp[]]);
printf("%d %d\n",temp[],it);
}else if(num==){
printf("%d %d\n",temp[],man[temp[]][]);
}
}
}