oj.uz

Submission #416855

# Submission time Handle Problem Language Result Execution time Memory
416855 2021-06-03T05:20:54 Z Collypso Jousting tournament (IOI12_tournament) C++17
100 / 100
 258 ms 43136 KB 
#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)
{
    for(; pos < sz(fenwick); pos += pos & -pos) fenwick[pos] += val;
}

int fenwick_get(int l, int 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)
{
    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();

    for(int i = 0; i < C; i++, cur_pointer++)
    {
        tree[cur_pointer].l = tree[seg_get(S[i] + 1)].l;
        tree[cur_pointer].r = tree[seg_get(E[i] + 1)].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);
            if (j == S[i]) seg_set(j + 1, cur_pointer);
            else seg_set(j + 1, 0);
        }
    }

    //for(int i = 1; i <= 2 * N; i++)
    //    cout << i << ": " << tree[i].to << " " << tree[i].l << " " << tree[i].r << endl;
    //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);

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

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


        if (height[i] - height[v] > mx_height)
            mx_height = height[i] - height[v], best_pos = i - 1;
        if (i <= N - 1)
        {
            fenwick_add(i, fenwick_get(i + 1, i + 1));
            fenwick_add(i + 1, -fenwick_get(i + 1, i + 1));
        }
        //cout << v << " " << tree[v].l << " " << tree[v].r << endl;
        //cout << endl;
    }

    //cout << mx_height << endl;

    return best_pos;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 1 ms 424 KB Output is correct
6 Correct 1 ms 428 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 588 KB Output is correct
2 Correct 10 ms 2252 KB Output is correct
3 Correct 6 ms 1868 KB Output is correct
4 Correct 11 ms 2200 KB Output is correct
5 Correct 11 ms 1996 KB Output is correct
6 Correct 9 ms 1996 KB Output is correct
7 Correct 10 ms 2252 KB Output is correct
8 Correct 10 ms 2124 KB Output is correct
9 Correct 7 ms 1868 KB Output is correct
10 Correct 11 ms 2124 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 19108 KB Output is correct
2 Correct 256 ms 43136 KB Output is correct
3 Correct 128 ms 35772 KB Output is correct
4 Correct 238 ms 42112 KB Output is correct
5 Correct 241 ms 41644 KB Output is correct
6 Correct 258 ms 38996 KB Output is correct
7 Correct 255 ms 43044 KB Output is correct
8 Correct 253 ms 43012 KB Output is correct
9 Correct 123 ms 35984 KB Output is correct
10 Correct 138 ms 36444 KB Output is correct