fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define gc getchar_unlocked
  4. #define fo(i,n) for(i=0;i<n;i++)
  5. #define Fo(i,k,n) for(i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
  6. #define ll long long
  7. #define si(x) scanf("%d",&x)
  8. #define sl(x) scanf("%lld",&x)
  9. #define ss(s) scanf("%s",s)
  10. #define pi(x) printf("%d\n",x)
  11. #define pl(x) printf("%lld\n",x)
  12. #define ps(s) printf("%s\n",s)
  13. #define pb push_back
  14. #define mp make_pair
  15. #define F first
  16. #define S second
  17. #define all(x) x.begin(), x.end()
  18. #define clr(x) memset(x, 0, sizeof(x))
  19. #define sortall(x) sort(all(x))
  20. #define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
  21. #define PI 3.1415926535897932384626
  22. typedef pair<int, int> pii;
  23. //typedef pair<ll, ll> pl;
  24. typedef vector<int> vi;
  25. typedef vector<ll> vl;
  26. typedef vector<pii> vpii;
  27. //typedef vector<pl> vpl;
  28. typedef vector<vi> vvi;
  29. typedef vector<vl> vvl;
  30. int mpow(int base, int exp);
  31. void ipgraph(int n, int m);
  32. void dfs(int u, int par);
  33. const int mod = 1000000007;
  34. const int N = 200003, M = N;
  35. //=======================
  36.  
  37. vi g[N];
  38. vi a;
  39. int n;
  40. const int rtn = 142;
  41. int cnt[N][rtn];
  42. int tot[rtn];
  43. int pl[N], bet[N];
  44. int id(int x){
  45. return x/rtn;
  46. }
  47. int solve(int x){
  48. // cout<<x<<endl;
  49. if(x<0) return -1;
  50. int sab = 0;
  51. for(int k: a)
  52. {
  53. sab += cnt[x][k];
  54. // cout<<k<<" ";
  55. }
  56. //cout<<endl<<sab<<" "<<tot[x]<<endl;
  57. if(sab == tot[x]) return solve(x-1);
  58. return x;
  59. }
  60. int mark[N], P, LA;
  61. int sol(int x, int w){
  62. if(x<0) return LA;
  63. int sab = cnt[x][w];
  64. if(sab==0) return sol(x-1, w);
  65. LA = x;
  66. for(int k: a)
  67. sab += cnt[x][k];
  68. if(sab==tot[x]) return sol(x-1, w);
  69. return x;
  70. }
  71. int win(int x){
  72. int i = x*rtn, j = min(n-1, i+rtn-1);
  73. int w;
  74.  
  75. Fo(w, j, i-1){
  76. if(!mark[pl[w]]){
  77. P = pl[w];
  78. return sol(x, P);
  79. }
  80. }
  81. }
  82.  
  83.  
  84. int main()
  85. {
  86. ios_base::sync_with_stdio(false);
  87. cin.tie(NULL);
  88. int i,k,j,q,x;
  89. cin>>n;
  90. int B;
  91. fo(i, n){
  92. int a, b;
  93. cin>>a>>b;
  94. pl[i] = a;
  95. bet[i] = b;
  96. //b[id(i)][a]
  97. cnt[id(i)][a]++;
  98. tot[id(i)]++;
  99. B = id(i);
  100. }
  101.  
  102. cin>>q;
  103. while(q--){
  104. cin>>k;
  105.  
  106.  
  107. a.clear();
  108. fo(i, k) cin>>x, a.pb(x), mark[x] = 1;
  109. x = solve(B);
  110. if(x==-1){
  111. cout<<0<<" "<<0<<endl;
  112. for(int x: a) mark[x] = 0;
  113. continue;
  114. }
  115. x = win(x);
  116. //x bucket mei P ki last bet
  117. int lo = x*rtn, hi = lo+rtn-1;
  118. hi = min(n-1, hi);
  119. int ans = 0;
  120. Fo(i, hi, lo-1){
  121. if(mark[pl[i]]) continue;
  122. if(pl[i]==P) ans = bet[i];
  123. else break;
  124. }
  125. cout << P<<" "<<ans << endl;
  126. for(int x: a) mark[x] = 0;
  127.  
  128. }
  129.  
  130.  
  131. return 0;
  132. }
  133.  
Success #stdin #stdout 0s 119104KB
stdin
6
1 10
2 100
3 1000
1 10000
2 100000
3 1000000
3
1 3
2 2 3
2 1 2
stdout
2 100000
1 10
3 1000