Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.BufferedReader;
- import java.io.IOException;
- import java.io.InputStreamReader;
- import java.io.PrintWriter;
- import java.util.Arrays;
- import java.util.StringTokenizer;
- import java.util.TreeSet;
- public class AuctionNlogN {
- private void solve() throws IOException {
- int n = readInt();
- int[] maxBet = new int[n];
- Arrays.fill(maxBet, -1);
- TreeSet<Integer>[] allBets = new TreeSet[n];
- for (int man = 0; man < n; man++) {
- allBets[man] = new TreeSet<>();
- }
- for (int i = 0; i < n; i++) {
- int man = readInt() - 1;
- int bet = readInt();
- allBets[man].add(bet);
- maxBet[man] = bet;
- }
- TreeSet<Integer> set = new TreeSet<>((a, b) -> {
- int res = Integer.compare(maxBet[a], maxBet[b]);
- if (res == 0) {
- res = Integer.compare(a, b);
- }
- return res;
- });
- for (int man = 0; man < n; man++) {
- if (allBets[man].size() > 0) {
- set.add(man);
- }
- }
- int q = readInt();
- for (int i = 0; i < q; i++) {
- int cnt = readInt();
- int[] absent = new int[cnt];
- for (int j = 0; j < cnt; j++) {
- absent[j] = readInt() - 1;
- }
- for (int man : absent) {
- set.remove(man);
- }
- if (set.isEmpty()) {
- out.println("0 0");
- } else {
- int winner = set.pollLast();
- if (set.isEmpty()) {
- out.println((winner + 1) + " " + allBets[winner].first());
- } else {
- int loser = set.last();
- out.println((winner + 1) + " " + allBets[winner].higher(maxBet[loser]));
- }
- set.add(winner);
- }
- for (int man : absent) {
- if (allBets[man].size() > 0) {
- set.add(man);
- }
- }
- }
- }
- //------------------------------------------------------------------------------
- public static void main(String[] args) {
- new AuctionNlogN().run();
- }
- private void run() {
- try {
- initIO();
- solve();
- in.close();
- out.close();
- } catch (Throwable e) {
- throw new RuntimeException(e);
- }
- }
- private BufferedReader in;
- private StringTokenizer tok;
- private PrintWriter out;
- private void initIO() throws IOException {
- in = new BufferedReader(new InputStreamReader(System.in));
- out = new PrintWriter(System.out);
- // in = new BufferedReader(new FileReader(new File("input.txt")));
- // out = new PrintWriter(new File("output.txt"));
- }
- private String readString() throws IOException {
- while (tok == null || !tok.hasMoreTokens()) {
- tok = new StringTokenizer(in.readLine());
- }
- return tok.nextToken();
- }
- @SuppressWarnings("unused")
- private int readInt() throws IOException {
- return Integer.parseInt(readString());
- }
- @SuppressWarnings("unused")
- private long readLong() throws IOException {
- return Integer.parseInt(readString());
- }
- @SuppressWarnings("unused")
- private double readDouble() throws IOException {
- return Double.parseDouble(readString());
- }
- }
Add Comment
Please, Sign In to add comment