Submission #416850

#	Time	Username	Problem	Language	Result	Execution time	Memory
416850		Collypso	Jousting tournament (IOI12_tournament)	C++17	0 / 100	257 ms	44844 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 = 1, int vr = global_N)
{
    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 = 1, int vr = global_N)
{
    if (vl == vr)
    {
        seg_tree[v] = !!val;
        seg_tree_pointer[vl] = val;
        return;
    }
    int vm = (vl + vr) / 2;
    if (pos <= seg_tree[v * 2 + 1]) seg_set(pos, val, v * 2 + 1, vl, vm);
    else seg_set(pos - seg_tree[v * 2 + 1], 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 = 1, int vr = global_N)
{
    if (vl == vr) return seg_tree_pointer[vl];
    int vm = (vl + vr) / 2;
    if (pos <= 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)
{
    //cout << v << " " << p << " " << d << endl;
    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)
{
    global_N = N, cur_pointer = N + 1;
    tree.resize(2 * (N + 1));
    for(int i = 1; i <= N; i++) tree[i] = {0, i, i};
    seg_tree_pointer.resize(N + 1); seg_tree.resize(4 * (N + 1));
    seg_build();

    //cout << "*********************" << endl;
    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 = E[i]; j >= S[i]; j--)
        {
            int pointer = seg_get(j + 1);
            tree[pointer].to = cur_pointer;
            tree[cur_pointer].children.pb(pointer);
            //cout << j + 1 << " " << pointer << " " << cur_pointer << endl;
            if (j == S[i]) seg_set(j + 1, cur_pointer);
            else seg_set(j + 1, 0);
        }
    }


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

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

    /*
    for(int i = 1; i <= 2 * N; i++) cout << height[i] << " ";
    cout << endl;

    //cout << "*********************" << endl;

    for(int i = 1; i <= 2 * N; i++)
    {
        cout << i << ": " << tree[i].to << endl;
        //for(int to : tree[i].children) cout << to << " ";
        //cout << endl;
    }
    */





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

    int mx_height = 0, best_pos = 0;
    for(int i = 1; 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;;
        if (height[i] - height[v] > mx_height)
            mx_height = height[i] - height[v], best_pos = i - 1;
        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 best_pos;
}


/*
5 3 3
1
0
2
4
1 3
0 1
0 1



100 90 62
95
97
89
51
12
41
31
29
17
0
24
19
61
46
45
32
50
25
18
75
28
16
7
20
49
59
44
35
4
87
67
76
63
69
64
37
56
42
40
54
5
8
47
85
84
91
33
11
9
36
66
78
96
83
82
93
65
86
70
55
60
73
81
79
3
43
13
26
99
21
48
38
39
23
15
53
6
22
1
2
52
14
58
34
30
27
10
57
74
72
77
94
90
68
80
98
92
71
88

31 32
63 64
63 64
25 26
36 37
61 62
44 45
44 45
43 44
43 44
43 44
24 25
51 52
50 51
10 11
10 11
67 68
4 5
4 5
3 4
3 4
3 4
46 47
5 6
5 6
5 6
5 6
4 5
4 5
68 69
22 23
21 22
20 21
20 21
20 21
19 20
19 20
19 20
19 21
18 19
18 19
18 19
4 5
3 5
8 9
7 8
6 7
6 7
6 7
5 6
4 5
3 5
2 3
1 2
0 1
0 2
24 25
23 24
23 24
23 24
22 23
22 23
16 17
15 16
14 15
14 15
14 15
13 14
13 14
13 14
13 15
12 13
11 12
10 11
9 10
9 10
9 10
8 9
7 9
6 7
5 6
5 6
5 6
4 5
4 5
4 5
3 4
2 4
2 3
0 3
*/

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