Submission #134670

#	Time	Username	Problem	Language	Result	Execution time	Memory
134670		PeppaPig	Jousting tournament (IOI12_tournament)	C++14	100 / 100	128 ms	23060 KiB

tournament

#include <bits/stdc++.h>

#define pii pair<int, int>
#define x first
#define y second

using namespace std;

const int N = 1<<17;

struct node {
    int mx, pos;
    vector<int> child;
} g[N<<1];

int n, R;
int idx[N], t[N], tmx[N<<1];

void update(int x, int k) { if(x <= n) t[x] += k, update(x + (x & -x), k); }

int query(int x) { return t[x] + (x ? query(x - (x & -x)) : 0); }

int get(int x) {
    int l = 1, r = n;
    while(l < r) {
        int mid = (l + r) >> 1;
        if(query(mid) >= x) r = mid;
        else l = mid + 1;
    }
    return r;
}

int query(int l, int r) {
    int ret = 0;
    for(l += N, r += N + 1; l < r; l >>= 1, r >>= 1) {
        if(l & 1) ret = max(ret, tmx[l++]);
        if(r & 1) ret = max(ret, tmx[--r]);
    }
    return ret;
}

int ans, ans_pos;

pii dfs(int u) {
    if(g[u].child.empty()) return pii(g[u].pos, g[u].pos);
    int l = n + 1, r = 0;
    g[u].pos = 1e9;
    for(int v : g[u].child) {
        pii now = dfs(v);
        l = min(l, now.x), r = max(r, now.y);
        if(g[v].mx > g[u].mx) g[u].mx = g[v].mx, g[u].pos = 1e9;
        if(g[v].mx == g[u].mx && g[v].pos < g[u].pos) g[u].pos = g[v].pos;
    }
    ++g[u].mx;
    if(query(l, r - 1) < R) {
        if(g[u].mx > ans) ans = g[u].mx, ans_pos = 1e9;
        if(g[u].mx == ans && g[u].pos < ans_pos) ans_pos = g[u].pos;
    }
    return pii(l, r);
}

int GetBestPosition(int _n, int C, int R, int *K, int *S, int *E) {
    n = _n, ::R = R;
    for(int i = 1; i <= n; i++) {
        update(i, 1);
        idx[i] = i, g[i].pos = i;
        tmx[i + N] = K[i-1];
    }
    for(int i = N-1; i; i--) tmx[i] = max(tmx[i<<1], tmx[i<<1|1]);
    for(int i = 1; i <= C; i++) {
        int s = S[i-1] + 1, e = E[i-1] + 1;
        vector<int> vec;
        for(int j = s; j <= e; j++) vec.emplace_back(get(j));
        for(int v : vec) {
            g[i + n].child.emplace_back(idx[v]);
            if(v != vec[0]) update(v, -1);
        }
        idx[vec[0]] = i + n;
    }
    dfs(n + C);
    return ans_pos - (ans_pos ? 1 : 0);
}

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