Submission #1193463

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193463		alexdd	마상시합 토너먼트 (IOI12_tournament)	C++20	100 / 100	67 ms	20804 KiB

tournament

#include<bits/stdc++.h>
using namespace std;

const int INF = 1e9;
const int MAXV = 3e5;

//vector<int> con[MAXV];
int parent[MAXV];
int anc[MAXV][20];
pair<int,int> pozs[MAXV];

int aib[MAXV];
int qry(int poz)
{
    poz+=2;
    int aux=0;
    for(int i=poz;i>0;i-=(i&(-i)))
        aux+=aib[i];
    return aux;
}
void upd(int poz, int newv)
{
    poz+=2;
    for(int i=poz;i<MAXV;i+=(i&(-i)))
        aib[i]+=newv;
}
int get_kth(int k)
{
    int st=0,dr=MAXV-5,ans=-1;
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        if(qry(mij) >= k)
        {
            ans = mij;
            dr = mij-1;
        }
        else
            st = mij+1;
    }
    assert(ans!=-1);
    return ans;
}
int myid[MAXV];
int tole[MAXV],tori[MAXV];
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E)
{
    for(int i=0;i<N;i++)
    {
        myid[i] = i;
        pozs[i] = {i,i};
        upd(i,+1);
        parent[i] = -1;
    }
    for(int i=0;i<C;i++)
    {
        pozs[N+i] = {INF, -1};
        for(int pas=0;pas<E[i]-S[i]+1;pas++)
        {
            int poz = get_kth(S[i]+1);
            //cerr<<N+i<<"  "<<poz<<" poz\n";
            upd(poz,-1);
            parent[myid[poz]] = N+i;
            pozs[N+i].first = min(pozs[N+i].first, pozs[myid[poz]].first);
            pozs[N+i].second = max(pozs[N+i].second, pozs[myid[poz]].second);
        }
        parent[N+i] = -1;
        myid[pozs[N+i].first] = N+i;
        upd(pozs[N+i].first, +1);
    }
    assert(qry(N)==1);
    //for(int i=0;i<N+C;i++)cerr<<i<<": "<<pozs[i].first<<" "<<pozs[i].second<<"   parent: "<<parent[i]<<"\n";

    for(int i=0;i<N+C;i++)
        anc[i][0]=parent[i];
    for(int p=1;p<20;p++)
        for(int i=0;i<N+C;i++)
        {
            if(anc[i][p-1]==-1)
                anc[i][p]=-1;
            else
                anc[i][p] = anc[anc[i][p-1]][p-1];
        }

    tole[0] = -1;
    for(int i=0;i<N-1;i++)
    {
        if(K[i] > R)
            tole[i+1] = i;
        else
            tole[i+1] = tole[i];
    }
    tole[N] = tole[N-1];

    tori[N] = N-1;
    for(int i=N-2;i>=0;i--)
    {
        if(K[i] > R)
            tori[i+1] = i;
        else
            tori[i+1] = tori[i+2];
    }
    tori[0] = tori[1];

    int mxm=-1,unde=-1;
    for(int i=0;i<N;i++)
    {

        int ple = tole[i] + 1;
        int pri = tori[i+1];

        int cur = i, cnt = 0;
        for(int p=19;p>=0;p--)
        {
            if(anc[cur][p]!=-1 && pozs[anc[cur][p]].first >= ple && pozs[anc[cur][p]].second <= pri)
            {
                cur = anc[cur][p];
                cnt += (1<<p);
            }
        }
        //cerr<<parent[cur]<<" parent\n";
        //cerr<<i<<" "<<cnt<<" cnt\n";
        if(cnt > mxm)
        {
            mxm = cnt;
            unde = i;
        }
    }
    return unde;
}

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