ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1439. Battle with You-Know-Who

Who can give me an ACed program? I got TLE on case #26...
Posted by --- 7 Oct 2006 08:55
I use Splay Tree to store the deleted number and Binary Search on N.
Re: Who can give me an ACed program? I got TLE on case #26...
Posted by Thunder 22 Dec 2007 16:05
//---------------------------------------------------------------------------

#include <stdio.h>

//---------------------------------------------------------------------------
int q[10001];

int GetPos(int x, int l, int r)
{
    if (l>=r)
        return l;
    if(q[(l+r)/2]<=x)
        return GetPos(x,(l+r)/2+1,r);
    else
        return GetPos(x,l,(l+r)/2);
}
//---------------------------------------------------------------------------
int main()
{
    int a=0;
    q[a]=2000000000;
    int n;
    char Key[2];
    int Val;
    scanf("%d%d",&n,&n);
    for(int i=0;i<n;i++)
    {
        scanf("%s%d",&Key,&Val);
        if(Key[0]=='L')
            printf("%d\n",Val+GetPos(Val,0,a));
        else
        {
            int Pos=GetPos(Val,0,a);
                for(int i=Pos;i<a;i++)
                    q[i]--;
            for(int i=a;i>Pos;i--)
                q[i]=q[i-1];
            q[Pos]=Val;
            q[++a]=2000000000;
        }
    }
    return 0;
}
//---------------------------------------------------------------------------
Re: Who can give me an ACed program? I got TLE on case #26...
Posted by Denis Koshman 12 Aug 2008 10:07
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <math.h>
#include <time.h>
#include <limits.h>
#include <assert.h>

#define FAIL *(int*)0 = 0

int a[16384];
int l[16384];
int r[16384];
int p[16384];
int h[16384];
int v[16384];
int root = -1;
int nn;

int n, m;

inline void upd(int x)
{
    h[x] = 0;
    v[x] = 1;

    if(l[x]>=0)
    {
        if(h[l[x]]+1 > h[x])
            h[x] = h[l[x]]+1;

        v[x] += v[l[x]];
    }

    if(r[x]>=0)
    {
        if(h[r[x]]+1 > h[x])
            h[x] = h[r[x]]+1;

        v[x] += v[r[x]];
    }
}

void fix(int x)
{
    while(x>=0)
    {
        int h1 = l[x]>=0 ? h[l[x]]+1 : 0;
        int h2 = r[x]>=0 ? h[r[x]]+1 : 0;

        if(h1 > h2+1 || h1==h2+1 && p[x]>=0 && r[p[x]]==x)
        {
            int a  = l[x];
            int b  = r[a];

            p[(p[x]>=0 ? l[p[x]]==x ? l[p[x]] : r[p[x]] : root) = a] = p[x];

            p[r[a]=x]=a;

            if((l[x]=b)>=0)
                p[b] = x, x = b;
        }
        else if(h2 > h1+1 || h2==h1+1 && p[x]>=0 && l[p[x]]==x)
        {
            int a = r[x];
            int b = l[a];

            p[(p[x]>=0 ? l[p[x]]==x ? l[p[x]] : r[p[x]] : root) = a] = p[x];

            p[l[a]=x]=a;

            if((r[x]=b)>=0)
                p[b] = x, x = b;
        }
        else
        {
            upd(x), x = p[x];
        }
    }
}

void add(int vv)
{
    int x;

    if(root==-1)
    {
        p[root = nn++] = -1, x = root;
    }
    else
    {
        x = root;

        for(;;)
        {
            assert(vv != a[x]);

            if(vv < a[x])
            {
                if(l[x]==-1)
                {
                    p[l[x]=nn++]=x, x=l[x];
                    break;
                }

                x = l[x];
            }
            else
            {
                if(r[x]==-1)
                {
                    p[r[x]=nn++]=x, x=r[x];
                    break;
                }

                x = r[x];
            }
        }
    }

    l[x] = r[x] = -1;
    a[x] = vv;
    fix(x);
}

inline int get(int vv)
{
    vv--;

    int cl = 1, cr = n;

    for(int x=root;x>=0;)
    {
        int nsl = a[x] - cl - (l[x]>=0 ? v[l[x]] : 0);

        if(vv < nsl)
            cr = a[x]-1, x = l[x];
        else
            vv -= nsl, cl = a[x]+1, x = r[x];
    }

    return cl+vv;
}

char c[128*1024];
int  x[128*1024];

int main()
{
//    freopen("input.txt", "r", stdin);

    scanf("%d %d", &n, &m);

    int i;
    for(i=0;i<m;i++)
    {
        char ts[4];
        scanf("%s %d", ts, x+i), c[i] = ts[0];
    }

    for(i=0;i<m;i++)
    {
        if(c[i]=='D')
            add(get(x[i]));
        else if(c[i]=='L')
            printf("%d\n", get(x[i]));
    }

    return 0;
}

Edited by author 12.08.2008 10:18
Re: Who can give me an ACed program? I got TLE on case #26...
Posted by Denis Koshman 12 Aug 2008 10:08
P.S: This is my custom AVL tree with only two simmetrical cases, specially for contests :)
(though it can perform at log^2(N), this rarely happens)

Edited by author 12.08.2008 10:17