Queue

#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int oo = 1e9;
const double PI = acos(-1);
const int N = 1e6;
int n, Queue[N];
struct node
{
    int high, more;
    bool operator < (const node &a) const
    {
        return high < a.high;
    }
} student[N];
struct da
{
    int left, right, sum;
} as[N*4];
void build(int left ,int right , int i)
{
    as[i].left = left;
    as[i].right = right;
    as[i].sum = right - left + 1;
    int mid = (left + right) / 2;
    if(left == right) return ;
    build(left, mid, 2*i);
    build(mid+1, right, 2*i+1);
}

void update(int i, int id)
{
    if(as[i].left == as[i].right && as[i].left == id)
    {
        as[i].sum = 0;
        return ;
    }
    if(id <= as[i*2].right) update(2*i, id);
    else update(2*i+1, id);
    as[i].sum = as[i*2].sum + as[i*2+1].sum;
}

int query(int i, int val, int sign)
{
    if(val > as[i].sum) return oo;/**< 如果这个位置已经有人了 或者 这个人没有位置可站了 */
    
    if(as[i].left == as[i].right) return as[i].left;

    if(sign == 1)
    {
        if(val <= as[i*2].sum) return query(2*i, val, sign);
        else return query(2*i+1, val - as[i*2].sum, sign);
    }

    if(sign == 0)
    {
        if(as[i*2+1].sum >= val) return query(2*i+1, val, sign);
        else return query(2*i, val-as[i*2+1].sum, sign);
    }
}

int main()
{
    int T, i, cas = 1, ok;
    scanf("%d", &T);
    while(T--)
    {
        ok = 0;
        memset(Queue, 0, sizeof(Queue));

        scanf("%d", &n);

        build(1, n, 1);

        for(i = 0; i < n; i++)
            scanf("%d %d", &student[i].high, &student[i].more);

        sort(student, student + n);/**< 按照身高排序 */

        for(i = 0; i < n; i++)
        {
            int l = query(1, student[i].more + 1, 1);/**< l，r 表示这个人可以插入的位置 */
            int r = query(1, student[i].more + 1, 0);
            int mini = min(l, r);/**<  找到最小的位置*/
            if(mini == oo)
            {
                ok = 1;
                break;
            }
            update(1, mini);
            Queue[mini] = student[i].high;
        }

        if(ok)
        {
            printf("Case #%d: impossible\n", cas++);
            continue;
        }
        printf("Case #%d:", cas++);
        for(i = 1; i <= n; i++)
            printf(" %d", Queue[i]);
        printf("\n");
    }
    return 0;
}