Submission #382721

#	Time	Username	Problem	Language	Result	Execution time	Memory
382721		ParsaAlizadeh	Jousting tournament (IOI12_tournament)	C++17	100 / 100	91 ms	21356 KiB

tournament

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

typedef long long       ll;
typedef pair<ll, ll>    pll;
typedef pair<int, int>  pii;

#define all(x)          x.begin(), x.end()
#define kill(x)         return cout << x << endl, 0
#define X               first
#define Y               second
#define endl            '\n'
#define lc              (id << 1)
#define rc              (lc | 1)

constexpr ll pw(ll a, ll b, ll mod) {
    return (!b    ? 1 :
            b & 1 ? a * pw(a * a % mod, b / 2, mod) % mod :
                    pw(a * a % mod, b / 2, mod));
}

constexpr int N   = 2e5 + 10;

int seg[N << 1], A[N], labl[N], sz[N], H[N], pos[N], ans[2];
vector<int> adj[N];

void Build(int id, int l, int r) {
    if (r - l == 1) {
        seg[id] = 1;
        return;
    }
    int mid = (l + r) >> 1;
    Build(lc, l, mid); Build(rc, mid, r);
    seg[id] = seg[lc] + seg[rc];
}

int Modify(int id, int l, int r, int ind, int val) {
    if (r - l == 1) {
        seg[id] = val;
        return l;
    }
    int mid = (l + r) >> 1, res;
    if (seg[lc] <= ind)
        res = Modify(rc, mid, r, ind - seg[lc], val);
    else
        res = Modify(lc, l, mid, ind, val);
    seg[id] = seg[lc] + seg[rc];
    return res;
}

int okey(int l, int r) {
    return (A[r] - A[l]) == 0;
}

void DFS(int u, int ind) {
    sz[u] = adj[u].empty();
    for (int v : adj[u]) {
        DFS(v, ind + sz[u]);
        sz[u] += sz[v];
        H[u] = max(H[u], H[v] + 1);
    }
    if (H[u] == 0) {
        pos[u] = ind;
        return;
    }
    if (!okey(ind, ind + sz[u] - 1))
        return;
    for (int v : adj[u]) if (H[v] + 1 == H[u]) {
        pos[u] = pos[v];
        break;
    }
    if (H[u] > ans[0] || (H[u] == ans[0] && pos[u] < ans[1]))
        ans[0] = H[u], ans[1] = pos[u];
}

int GetBestPosition(int n, int C, int R, int *K, int *S, int *E) {
    Build(1, 0, n);
    iota(labl, labl + n, 0);
    int timer = n;
    for (int i = 0; i < C; i++) {
        int l = Modify(1, 0, n, S[i], 1);
        adj[timer].push_back(labl[l]);
        for (int j = 0; j < E[i] - S[i]; j++) {
            int r = Modify(1, 0, n, S[i] + 1, 0);
            adj[timer].push_back(labl[r]);
        }
        labl[l] = timer++;
    }
    int root = timer - 1; //labl[Modify(1, 0, n, 0, 1)];
    for (int i = 1; i < n; i++) {
        A[i] = A[i - 1] + (K[i - 1] > R);
    }
    DFS(root, 0);
    return ans[1];
}

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