Submission #237586

#	Time	Username	Problem	Language	Result	Execution time	Memory
237586		nicolaalexandra	Jousting tournament (IOI12_tournament)	C++14	100 / 100	563 ms	26596 KiB

tournament

#include <bits/stdc++.h>
#define DIM 100010
#define INF 2000000000
using namespace std;

int n,r,c,i,j;

int aib[DIM*2],v[DIM],stramos[DIM*2][22],aint[DIM*4];
set <pair<int,int> > s;
pair<int,int> intv[DIM*2];

void update_aib (int p, int val){
    for (;p<=n;p+=(p&-p))
        aib[p] += val;
}
int query (int p){
    if (p <= 0)
        return 0;
    int sol = 0;
    for (;p;p-=(p&-p))
        sol += aib[p];
    return sol;
}

int find_kth (int k){

    int st = 1, dr = n, sol = 0;
    while (st <= dr){
        int mid = (st+dr)>>1;
        if (query(mid) >= k){
            sol = mid;
            dr = mid-1;
        } else st = mid+1;
    }
    return sol;
}

void build (int nod, int st, int dr){
    if (st == dr){
        aint[nod] = v[st];
        return;
    }
    int mid = (st+dr)>>1;
    build (nod<<1,st,mid);
    build ((nod<<1)|1,mid+1,dr);
    aint[nod] = max (aint[nod<<1],aint[(nod<<1)|1]);
}

void update (int nod, int st, int dr, int poz, int val){
    if (st == dr){
        aint[nod] = val;
        return;
    }
    int mid = (st+dr)>>1;
    if (poz <= mid)
        update (nod<<1,st,mid,poz,val);
    else update ((nod<<1)|1,mid+1,dr,poz,val);
    aint[nod] = max (aint[nod<<1],aint[(nod<<1)|1]);
}

int query (int nod, int st, int dr, int x, int y){
    if (x <= st && dr <= y)
        return aint[nod];
    int mid = (st+dr)>>1, sol_st = 0, sol_dr = 0;
    if (x <= mid)
        sol_st = query (nod<<1,st,mid,x,y);
    if (y > mid)
        sol_dr = query ((nod<<1)|1,mid+1,dr,x,y);
    return max (sol_st,sol_dr);
}

int GetBestPosition (int N, int C, int R, int *K, int *S, int *E) {
    n = N, r = R+1, c = C;

    for (i=1;i<=n;i++){
        update_aib (i,1);
        s.insert(make_pair(i,i));
        intv[i] = make_pair(i,i);
    }

    int idx = n;

    for (i=1;i<=c;i++){
        idx++;

        int x = S[i-1] + 1, y = E[i-1] + 1;
        int poz = find_kth(x);

        set <pair<int,int> > :: iterator it = s.lower_bound(make_pair(poz,0)), it2;
        it2 = it;

        int maxi = 0, mini = INF;
        /// sterg tot intervalul care incepe la poz
        for (int pas=1;pas<=y-x+1;pas++){
            mini = min (mini,intv[it2->second].first);
            maxi = max (maxi,intv[it2->second].second);

            stramos[it2->second][0] = idx;

            update_aib(it2->first,-1);
            it2++;
        }

        s.erase(it,it2);
        s.insert(make_pair(poz,idx));
        update_aib(poz,1);
        intv[idx] = make_pair(mini,maxi);
    }

    for (j=1;j<=20;j++)
        for (i=1;i<=n+c;i++)
            stramos[i][j] = stramos[stramos[i][j-1]][j-1];

    v[1] = 0;
    for (i=2;i<=n;i++){
        if (K[i-2]+1 < r)
            v[i] = 0;
        else v[i] = 1;
    }

    build (1,1,n);

    int sol = 0, best_poz = 1;
    for (i=1;i<=n;i++){

        /// vreau sa vad cat de mult ma pot duc in sus a.i. sa am numai 0 in subarbore
        int nod = i, nr = 0;
        for (j=20;j>=0;j--){
            int nod_aux = stramos[nod][j];
            if (!nod_aux)
                continue;

            int st = intv[nod_aux].first , dr = intv[nod_aux].second;
            int maxi = query (1,1,n,st,dr);
            if (!maxi){ /// e subarbore ok, deci pot sa urc
                nod = nod_aux;
                nr += (1<<j);
            }
        }

        if (nr > sol){
            sol = nr;
            best_poz = i;
        }

        if (i == n)
            break;

        /// fac swap intre v[i] si v[i+1]
        int aux = v[i], aux2 = v[i+1];
        update (1,1,n,i,aux2);
        update (1,1,n,i+1,aux);
        swap (v[i],v[i+1]);
    }

    return best_poz-1;

}

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