【题目链接】:http://codeforces.com/problemset/problem/749/D
【题意】
有n个人在竞价;
按照时间的顺序给出n次竞价(可能有一些人没有参加竞价);
每次竞价以竞价人的编号和竞价给出;
保证竞价严格递增;
且同一个人不会连续竞价两次;
现在,假设去掉某一些竞价的人;
问你最后谁是那个竞价成功的人?
如果去掉一些人之后,出现了某人连续竞价两次;
则取最小的价格(但要使得他依然能竞价成功);
每次输出winner和它的最小竞价;
【题解】
每个人的有用信息只有它的最高竞价(对于排名来说);
其他的都不重要的,因为去掉之后;
你的其他竞价都不存在了;
而最高竞价额才能影响某个人最后的排名;
则维护每个人的最高竞价;
如果删除了某个人只要删除它的最高竞价就好;
这样其他人的最高竞价还存着;
就能快速获取最高的那个竞价人是谁了;
用个map就能搞定;
然后获取第二大的人;
只要比第二大的人的最高竞价高,然后最小,就是答案了;
所以还需要记录每个人的所有竞价的价格,用于最后找最小的竞价;
查询大于某个价格且最小,用lower_bound就好;
【Number Of WA】
0
【完整代码】
#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ms(x,y) memset(x,y,sizeof x)
#define Open() freopen("D:\\rush.txt","r",stdin)
#define Close() ios::sync_with_stdio(0),cin.tie(0)
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
const int dx[9] = { 0,1,-1,0,0,-1,-1,1,1 };
const int dy[9] = { 0,0,0,-1,1,-1,1,-1,1 };
const double pi = acos(-1.0);
const int N = 2e5+100;
int n,a[N],b[N],mx[N],l[N];
map <int,int> dic;
vector <int> v[N];
int main()
{
//Open();
Close();//scanf,puts,printf not use
//init??????
cin >> n;
rep1(i,1,n)
{
int x,y;
cin >> x >> y;
mx[x] = y;
v[x].pb(y);
}
rep1(i,1,n)
if (mx[i])
dic[mx[i]] = i;
cin >> n;
dic[0] = 0;
rep1(i,1,n)
{
int k;
cin >> k;
rep1(j,1,k)
{
cin >> l[j];
if (mx[l[j]])
dic.erase(mx[l[j]]);
}
map<int,int>::iterator p = dic.end();
p--;
if (p==dic.begin())
cout <<"0 0"<<endl;
else
{
int id = p->se;
p--;
cout<<id<<' '<<*lower_bound(v[id].begin(),v[id].end(),p->fi)<<endl;
}
rep1(j,1,k)
if (mx[l[j]])
dic[mx[l[j]]] = l[j];
}
return 0;
}