Submission #7747

#	Time	Username	Problem	Language	Result	Execution time	Memory
7747		dohyun0324	Jousting tournament (IOI12_tournament)	C++98	100 / 100	204 ms	12784 KiB

tournament

#include<stdio.h>
#include<algorithm>
using namespace std;
int m,p,n,c=2,r,tree2[300010],t=1,dap,top,a[300010];
struct data3
{
    int l,r;
}tree[2][300010];
struct data2
{
    int e,val;
}st[300010];
struct data
{
    int s,e,val;
    bool operator<(const data&r)const
    {
        if(s==r.s) return e>r.e;
        return s<r.s;
    }
}arr[100010];
int max(int x,int y)
{
    if(x>y) return x;
    return y;
}
void find(int x,int k,int s,int e,int sw)
{
    if(k>=t)
    {
        p=k-t+1;
        return;
    }
    if(x<=tree[sw][k].l)
    {
        find(x,k*2,s,(s+e)/2,sw);
    }
    else
    {
        x-=tree[sw][k].l;
        find(x,k*2+1,(s+e)/2+1,e,sw);
    }
}
void update(int k,int x,int y,int s,int e,int sw)
{
    if(x>e || y<s) return;
    if(s<=x && y<=e){tree[sw][k].l=0; tree[sw][k].r=0; return;}
    update(k*2,x,(x+y)/2,s,e,sw);
    update(k*2+1,(x+y)/2+1,y,s,e,sw);
    tree[sw][k].l=tree[sw][k*2].l+tree[sw][k*2].r;
    tree[sw][k].r=tree[sw][k*2+1].l+tree[sw][k*2+1].r;
}
int query(int k,int x,int y,int s,int e)
{
    if(x>e || y<s) return 0;
    if(s<=x && y<=e) return tree2[k];
    return max(query(k*2,x,(x+y)/2,s,e),query(k*2+1,(x+y)/2+1,y,s,e));
}
int GetBestPosition(int n, int m, int r, int *K, int *x, int *y)
{
    int i,cnt=0,w;
    for(i=n;i>=1;i--)
    {
        a[i]=K[i-2];
    }
    a[1]=r;
    for(i=1;;i++)
    {
        t*=2;
        if(t>=n) break;
    }
    p=t/2;
    for(i=1;i<=t-1;i++)
    {
        if(i==c) p/=2, c*=2;
        tree[0][i].l=p; tree[0][i].r=p;
        tree[1][i].l=p; tree[1][i].r=p;
    }
    for(i=t;i<=t*2-1;i++) tree[0][i].l=1, tree[1][i].l=1;
    for(i=1;i<=m;i++)
    {
        x[i-1]++; y[i-1]++;
        find(x[i-1],1,1,t,0); arr[i].s=p;
        find(y[i-1],1,1,t,1); arr[i].e=p;
        update(1,1,t,arr[i].s+1,arr[i].e,0);
        update(1,1,t,arr[i].s,arr[i].e-1,1);
    }
    for(i=t;i<=t*2-1;i++)
    {
        tree2[i]=a[i-t+1];
    }
    for(i=t-1;i>=1;i--)
    {
        tree2[i]=max(tree2[i*2],tree2[i*2+1]);
    }
    for(i=1;i<=m;i++)
    {
        arr[i].val=query(1,1,t,arr[i].s+1,arr[i].e);
    }
    sort(arr+1,arr+m+1);
    top++; st[top].e=arr[1].e; st[top].val=arr[1].val;
    if(st[top].val<r) cnt++;
    if(dap<cnt)
    {
        dap=cnt;
        w=1;
    }
    for(i=2;i<=m;i++)
    {
        while(st[top].e<arr[i].e)
        {
            if(st[top].val<r) cnt--;
            st[top].e=0; st[top].val=0; top--;
        }
        top++; st[top].e=arr[i].e; st[top].val=arr[i].val;
        if(st[top].val<r) cnt++;
        if(dap<cnt)
        {
            dap=cnt;
            w=i;
        }
    }
    return arr[w].s-1;
}

• Subtask 1: 17 / 17
• Subtask 2: 32 / 32
• Subtask 3: 51 / 51