Submission #43818

#	Time	Username	Problem	Language	Result	Execution time	Memory
43818		PowerOfNinjaGo	Jousting tournament (IOI12_tournament)	C++14	100 / 100	683 ms	40740 KiB

tournament

//Power Of Ninja Go
#include <bits/stdc++.h>
#ifdef atom
    #include "grader.cpp"
#else
#endif
using namespace std;
typedef long long ll; typedef pair<int, int> ii;
#define X first
#define Y second
#define vi vector<int>
#define vii vector< ii >
#define pb push_back
const int maxn = 1e5+5;
int arr[maxn];
vi adj[2*maxn];
int lo[2*maxn];
int hi[2*maxn];
int st[4*maxn];
int dp[22][2*maxn];
int n;
struct node
{
    int v, sz, prio;
    node *left, *right;
    void upd()
    {
        sz = 1+(left?left->sz:0)+(right?right->sz:0);
    }
    node(int a)
    {
        v = a; left = right = NULL;
        prio = (rand()<<16)^rand();
        upd();
    }
};
node *root = NULL;
node* merge(node *L, node *R)
{
    if(!L || !R) return L?L:R;
    if(L->prio > R->prio)
    {
        L->right = merge(L->right, R);
        L->upd();
        return L;
    }
    else
    {
        R->left = merge(L, R->left);
        R->upd();
        return R;
    }
}
void split(node *u, node* &L, node* &R, int cur)
{
    L = R = NULL;
    if(!u) return;
    int k = 1+(u->left?u->left->sz:0);
    if(k<= cur)
    {
        L = u;
        split(u->right, u->right, R, cur-k);
    }
    else
    {
        R = u;
        split(u->left, L, u->left, cur);
    }
    u->upd();
}
void transfer(int dest, node *u)
{
    if(u == NULL) return;
    lo[dest] = min(lo[dest], lo[u->v]);
    hi[dest] = max(hi[dest], hi[u->v]);
    adj[dest].pb(u->v);
    //printf("connect %d to %d\n", dest, u->v);
    transfer(dest, u->left); transfer(dest, u->right);
}
void process(int x, int y, int dest)
{
    node *v, *w;
    split(root, root, v, y+1);
    split(root, root, w, x);
    transfer(dest, w);
    root = merge(root, new node(dest));
    root = merge(root, v);
    //printf("%d\n", u->sz);
}
void buildseg(int p = 1, int L = 0, int R = n-2)
{
    if(L == R)
    {
        st[p] = arr[L];
        return;
    }
    int M = (L+R)/2;
    buildseg(2*p, L, M); buildseg(2*p+1, M+1, R);
    st[p] = max(st[2*p], st[2*p+1]);
}
int ask(int i, int j, int p = 1, int L = 0, int R = n-2)
{
    if(i> R || j< L) return 0;
    if(i<= L && R<= j) return st[p];
    int M = (L+R)/2;
    int x = ask(i, j, 2*p, L, M); int y = ask(i, j, 2*p+1, M+1, R);
    return max(x, y);
}
void dfs(int u)
{
    for(auto v : adj[u])
    {
        dp[0][v] = u;
        dfs(v);
    }
}
void trav(node *u)
{
    if(u == NULL) return;
    //printf("trav %d\n", u->v);
    dp[0][u->v] = -1;
    dfs(u->v);
    trav(u->left); trav(u->right);
}
int GetBestPosition(int N, int c, int r, int *k, int *s, int *e)
{
    n = N;
    for(int i = 0; i< n-1; i++) arr[i] = k[i];
    for(int i = 0; i< n; i++) root = merge(root, new node(i));
    int cur = n;
    for(int i = 0; i< n; i++) lo[i] = hi[i] = i;
    for(int i = 0; i< n; i++) dp[0][i] = -1;
    for(int i = 0; i< c; i++)
    {
        lo[cur] = 1e9, hi[cur] = -1e9;
        process(s[i], e[i], cur);
        cur++;
    }
    trav(root);
    for(int i = 1; i<= 20; i++)
    {
        for(int j = 0; j< cur; j++)
        {
            int x = dp[i-1][j];
            if(x == -1) dp[i][j] = -1;
            else dp[i][j] = dp[i-1][x];
        }
    }
    int best = 0, dat = 0;
    buildseg();
    for(int i = 0; i< n; i++)
    {
        int now = i;
        int cnt = 0;
        for(int p = 20; p>= 0; p--)
        {
            int tobe = dp[p][now];
            if(tobe == -1) continue;
            //printf("%d tobe %d\n", i, tobe);
            int rangeX = lo[tobe], rangeY = hi[tobe]-1;
            int val = ask(rangeX, rangeY);
            //printf("[%d, %d]\n", rangeX, rangeY);
            //printf("val is %d\n", val);
            if(val<= r)
            {
                now = tobe;
                cnt += 1<<p;
            }
        }
        //printf("%d is %d\n", i, cnt);
        if(cnt> best)
        {
            best = cnt;
            dat = i;
        }
    }
    return dat;
}

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