Cod sursă (job #96256)

#include <stdio.h>
#include <algorithm>

using namespace std;

const int N=5000002;
int poz[N],val[N];

bool cmp (int a, int b)
{
    return (val[a]<val[b]);
}

int main()
{
    FILE *in,*out;
    in=fopen("lalele.in","r");
    out=fopen("lalele.out","w");

    int n,i,j,q,z,d,x,aux,nr=0,k,floare=0;

    fscanf(in,"%d",&n);
    z=0;
    while(n>0)
    {
        fscanf(in,"%d%d",&d,&x);
        if(x==0)
        {
            for(i=0;i<d;i++)
            {
                k=(nr>>1)+1;
                if(nr>k)
                    nth_element(poz+1,poz+k,poz+nr+1,cmp);
                else if(k==2 && val[poz[1]]>val[poz[2]])
                {
                    aux=poz[1];
                    poz[1]=poz[2];
                    poz[2]=aux;
                }
                fprintf(out,"%d\n",val[poz[k]]+z);
                //actualizeaza vectorul
                q=0;
                for(j=1;q<(nr>>1);j++)
                {
                    if(val[poz[j]]<=val[poz[k]] && q<(nr>>1))
                        poz[++q]=poz[j];
                }
                nr>>=1;
                z++;
            }
        }
        else
        {
            for(i=0;i<d;i++)
            {
                floare++;
                nr++;
                poz[nr]=floare;
                val[floare]=x-z;
                z++;
            }
        }
        n-=d;
    }
    return 0;
}