Submission #5941784

---

Source Code Expand

using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Math;

class Program
{
    static void Main()
    {
        SetOut(new System.IO.StreamWriter(OpenStandardOutput()) { AutoFlush = false });
        var Q = int.Parse(ReadLine());
        var bit = new BIT(2000001);
        for (int i = 0; i < Q; i++)
        {
            var TX = ReadLine().Split();
            var X = int.Parse(TX[1]);
            if (TX[0] == "1")
            {
                bit.Add(X, 1);
            }
            else
            {
                var a = bit.LowerBound(X);
                WriteLine(a);
                bit.Add(a, -1);
            }
        }
        Out.Flush();
    }
}

public class BIT
{
    int[] buffer;
    int root;

    public BIT(int length)
    {
        buffer = new int[length + 1];
        root = 1 << 30;
        while (root > length) root >>= 1;
    }

    public void Add(int index, int value)
    {
        for (int i = index + 1; i < buffer.Length; i += i & -i) buffer[i] += value;
    }

    public int Sum(int index)
    {
        int ret = 0;
        for (int i = index; i > 0; i -= i & -i) ret += buffer[i];
        return ret;
    }

    public int Sum(int l, int r)
    {
        return Sum(r) - Sum(l);
    }

    public int LowerBound(int w)
    {
        int x = 0;
        for (int k = root; k > 0; k >>= 1)
        {
            if (x + k < buffer.Length && buffer[x + k] < w)
            {
                w -= buffer[x + k];
                x += k;
            }
        }
        return x;
    }
}

Submission Info

Judge Result