Submission #56352

#	Time	Username	Problem	Language	Result	Execution time	Memory
56352		aquablitz11	Jousting tournament (IOI12_tournament)	C++14	100 / 100	325 ms	46240 KiB

tournament

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

using pii = pair<int, int>;
const int N = 200010;
const int LN = 18;

int n, ptr[N], nxt[N], ft[N];

int get(int x) {
    ++x;
    int i = 0, c = 0;
    for (int j = LN-1; j >= 0; --j) {
        int ni = i+(1<<j);
        if (ni <= n && ni-(c+ft[ni]) < x) {
            i = ni;
            c += ft[ni];
        }
    }
    return i;
}

int skip(int x) {
    if (nxt[x] == x) return x;
    return nxt[x] = skip(nxt[x]);
}

void upd(int i) {
    nxt[i] = i+1;
    for (++i; i <= n; i += i&-i)
        ft[i] += 1;
}

int cnt;
vector<int> G[N*2];
int in[N*2], out[N*2], tick, par[N*2][LN], seg[N*4], dep[N*2];

void dfs(int u, int p)
{
    dep[u] = dep[p]+1;
    in[u] = tick++;
    par[u][0] = p;
    for (int i = 1; i < LN; ++i)
        par[u][i] = par[par[u][i-1]][i-1];
    for (auto v : G[u])
        dfs(v, u);
    out[u] = tick;
}

void updseg(int p, int x)
{
    for (seg[p += cnt] = x; p > 1; p >>= 1)
        seg[p>>1] = max(seg[p], seg[p^1]);
}

int getmax(int l, int r)
{
    int ans = 0;
    for (l += cnt, r += cnt; l < r; l >>= 1, r >>= 1) {
        if (l&1) ans = max(ans, seg[l++]);
        if (r&1) ans = max(ans, seg[--r]);
    }
    return ans;
}

int trylift(int s, int r)
{
    int u = s;
    for (int i = LN-1; i >= 0; --i) {
        int v = par[u][i];
        if (getmax(in[v], out[v]) == r)
            u = v;
    }
    return dep[s]-dep[u];
}

int GetBestPosition(int n, int c, int r, int *K, int *S, int *E)
{
    ::n = n;
    cnt = n;
    for (int i = 0; i < n; ++i)
        ptr[i] = i, nxt[i] = i;
    nxt[n] = n;
    for (int i = 0; i < c; ++i) {
        int s = get(S[i]);
        int e = get(E[i]);
        for (int j = s; j <= e; j = skip(j)) {
            G[cnt].push_back(ptr[j]);
            if (j != s) {
                ptr[j] = -1;
                upd(j);
            } else {
                ++j;
            }
        }
        ptr[s] = cnt++;
    }
    dfs(cnt-1, cnt-1);

    updseg(in[0], r);
    for (int i = 0; i < n-1; ++i)
        updseg(in[i+1], K[i]);
    pii ans(trylift(0, r), 0);
    for (int i = 1; i < n; ++i) {
        updseg(in[i], r);
        updseg(in[i-1], K[i-1]);
        ans = max(ans, pii(trylift(i, r), -i));
    }

    return -ans.second;
}

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