Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- import java.io.*;
- import java.math.BigInteger;
- import java.awt.geom.Point2D;
- public class Main implements Runnable {
- Map<Integer, Integer> compressed;
- Map<Integer, Integer> real;
- private void solution() throws IOException {
- int ts = in.nextInt();
- while (ts-- > 0) {
- int n = in.nextInt();
- compressed = new HashMap<Integer, Integer>();
- real = new HashMap<Integer, Integer>();
- List<Integer> all = new ArrayList<Integer>();
- for (int i = 0; i < n; ++i) {
- int x = in.nextInt();
- all.add(x);
- }
- int m = in.nextInt();
- int[] req = new int[n + m];
- Arrays.fill(req, Integer.MAX_VALUE);
- for (int i = 0; i < n; ++i) {
- req[i] = all.get(i);
- }
- for (int i = 0; i < m; ++i) {
- String command = in.next();
- if (command.equals("add")) {
- int x = in.nextInt();
- req[n + i] = x;
- all.add(x);
- }
- }
- Collections.sort(all);
- compress(all);
- int size = Integer.highestOneBit(all.size()) << 1;
- int[] sum = new int[size * 2];
- for (int i = 0; i < req.length; ++i) {
- if (req[i] == Integer.MAX_VALUE) {
- out.println(real.get(get(1, (sum[1] + 1) / 2, sum) - size));
- } else {
- add(compressed.get(req[i]), sum);
- }
- }
- }
- }
- private int get(int at, int need, int[] sum) {
- if (2 * at >= sum.length) {
- return at;
- }
- if (sum[2 * at] >= need) {
- return get(2 * at, need, sum);
- } else {
- return get(2 * at + 1, need - sum[2 * at], sum);
- }
- }
- private void add(int i, int[] sum) {
- i += sum.length >> 1;
- while (i > 0) {
- ++sum[i];
- i >>= 1;
- }
- }
- private void compress(List<Integer> all) {
- for (int x : all) {
- if (!compressed.containsKey(x)) {
- int size = compressed.size();
- compressed.put(x, size);
- real.put(size, x);
- }
- }
- }
- @Override
- public void run() {
- try {
- solution();
- in.reader.close();
- out.close();
- } catch (IOException e) {
- e.printStackTrace();
- System.exit(1);
- }
- }
- private class Scanner {
- BufferedReader reader;
- StringTokenizer tokenizer;
- public Scanner(Reader reader) {
- this.tokenizer = new StringTokenizer("");
- this.reader = new BufferedReader(reader);
- }
- public boolean hasNext() throws IOException {
- while (!tokenizer.hasMoreTokens()) {
- String line = reader.readLine();
- if (line == null) {
- return false;
- }
- tokenizer = new StringTokenizer(line);
- }
- return true;
- }
- public String next() throws IOException {
- hasNext();
- return tokenizer.nextToken();
- }
- public String nextLine() throws IOException {
- tokenizer = new StringTokenizer("");
- return reader.readLine();
- }
- public int nextInt() throws IOException {
- return Integer.parseInt(next());
- }
- }
- public static void main(String[] args) {
- new Thread(null, new Main(), "Main", 1 << 28).start();
- }
- Scanner in = new Scanner(new InputStreamReader(System.in));
- PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement