Submission #416589

#	Time	Username	Problem	Language	Result	Execution time	Memory
416589		Collypso	Jousting tournament (IOI12_tournament)	C++17	0 / 100	89 ms	19692 KiB

tournament

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vt vector
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
#pragma GCC optimize ("O3")
#pragma GCC optimize ("O2")
#define F first
#define S second
//#define endl '\n'
//#define int long long

#define inbuf_len 1 << 16
#define outbuf_len 1 << 16

using namespace std;

int global_N;
vt<int> seg_tree, seg_tree_pointer;

void seg_build(int v = 0, int vl = 0, int vr = global_N - 1)
{
    if (vl == vr)
    {
        seg_tree[v] = 1;
        seg_tree_pointer[vl] = vl;
        return;
    }
    int vm = (vl + vr) / 2;
    seg_build(v * 2 + 1, vl, vm);
    seg_build(v * 2 + 2, vm + 1, vr);
    seg_tree[v] = seg_tree[v * 2 + 1] + seg_tree[v * 2 + 2];
}

void seg_set(int pos, int val, int v = 0, int vl = 0, int vr = global_N - 1)
{
    if (vl == vr)
    {
        seg_tree[v] = !!val;
        seg_tree_pointer[vl] = val;
        return;
    }
    int vm = (vl + vr) / 2;
    if (pos <= vm) seg_set(pos, val, v * 2 + 1, vl, vm);
    else seg_set(pos, val, v * 2 + 2, vm + 1, vr);
    seg_tree[v] = seg_tree[v * 2 + 1] + seg_tree[v * 2 + 2];
}

int seg_get(int pos, int v = 0, int vl = 0, int vr = global_N - 1)
{
    if (vl == vr) return seg_tree_pointer[vl];
    int vm = (vl + vr) / 2;
    if (pos + 1 <= seg_tree[v * 2 + 1]) return seg_get(pos, v * 2 + 1, vl, vm);
    else return seg_get(pos - seg_tree[v * 2 + 1], v * 2 + 2, vm + 1, vr);
}

vt<int> fenwick;

void fenwick_add(int pos, int val)
{
    pos++;
    for(; pos < sz(fenwick); pos += pos & -pos) fenwick[pos] += val;
}

int fenwick_get(int l, int r)
{
    l++, r++;
    int sumL = 0, sumR = 0;
    for(l--; l > 0; l -= l & -l) sumL += fenwick[l];
    for(; r > 0; r -= r & -r) sumR += fenwick[r];
    return sumR - sumL;
}

struct node
{
    int to, l, r;
    vt<int> children;

    node() {}

    node(int to_, int l_, int r_) { to = to_, l = l_, r = r_; }
};

vt<node> tree;
int cur_pointer;

vt<int> height;
vt<vt<int>> parent;
int lg;

void dfs(int v, int p, int d = 0)
{
    height[v] = d; parent[v][0] = p;
    for(int i = 1; i <= lg; i++) parent[v][i] = parent[parent[v][i - 1]][i - 1];
    for(int to : tree[v].children) dfs(to, v, d + 1);
}

int GetBestPosition(int N, int C, int R, int* K, int* S, int* E)
{
    tree.resize(2 * N); global_N = cur_pointer = N;
    for(int i = 0; i < N; i++) tree[i] = {0, i, i};
    seg_tree_pointer.resize(N); seg_tree.resize(4 * N); seg_build();
    for(int i = 0; i < C; i++, cur_pointer++)
    {
        tree[cur_pointer].l = tree[seg_get(S[i])].l;
        tree[cur_pointer].r = tree[seg_get(E[i])].r;
        for(int j = S[i]; j <= E[i]; j++)
        {
            int pointer = seg_get(j);
            tree[pointer].to = cur_pointer;
            tree[cur_pointer].children.pb(pointer);
        }
        for(int j = S[i]; j <= E[i]; j++) seg_set(j, 0);
        seg_set(S[i], cur_pointer);
    }

    lg = ceil(log2(2 * N)) + 1;
    parent.resize(2 * N, vt<int>(lg + 1)); height.resize(2 * N);
    dfs(cur_pointer - 1, cur_pointer - 1);

    /*
    for(auto x : parent)
    {
        for(auto y : x) cout << y << " ";
        cout << endl;
    }
    cout << endl;

    for(node x : tree) cout << x.to << "  " << x.l << " " << x.r << endl;
    */

    fenwick.resize(N + 1);
    for(int i = 0; i < N - 1; i++)
        if (K[i] > R) fenwick_add(i + 1, 1);

    int mx_height = 0;
    for(int i = 0; i < N; i++)
    {
        int v = i;
        for(int k = lg; k >= 0; k--)
            if (!fenwick_get(tree[parent[v][k]].l, tree[parent[v][k]].r)) v = parent[v][k];
        //cout << i << " " << v << endl;
        //for(int j = 0; j < N; j++) cout << fenwick_get(j, j) << " ";
        //cout << endl << "***" << endl;
        mx_height = max(mx_height, height[i] - height[v]);
        if (i < N - 1)
        {
            fenwick_add(i, fenwick_get(i + 1, i + 1));
            fenwick_add(i + 1, -fenwick_get(i + 1, i + 1));
        }
    }



    return mx_height;
}

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