Submission #761443

#	Time	Username	Problem	Language	Result	Execution time	Memory
761443		fatemetmhr	Jousting tournament (IOI12_tournament)	C++17	100 / 100	84 ms	69140 KiB

tournament

//  ~ Be Name Khoda ~  //

#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  1e6   + 10;
const int maxn5 =  (1 << 19)   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   + 7;
const int lg    =  19;
const ll  inf   =  1e18;

vector <int> adj[maxn5];
int par[lg][maxn5], l[maxn5], pre[maxn5];
int r[maxn5], id[maxn5], nxt[maxn5], pos[maxn5];

namespace fen{

    int fen[maxn5];

    inline void add(int id, int val){
        for(++id; id < maxn5; id += id & -id)
            fen[id] += val;
    }

    inline int find(int k){
        //cout << "finding " << k << endl;
        int id = 0;
        for(int i = lg - 1; i >= 0; i--){
            //cout << "check for " << i << ' ' << id << ' ' << k << ' ' << fen[id + (1 << i)] << endl;
            if(fen[id + (1 << i)] < k){
                id += (1 << i);
                k -= fen[id];
            }
        }
        //cout << "id of " << id << ' ' << k << endl;
        return id;
    }
}

void dfs(int v){
    //cout << "ok " << v << ' ' << par[0][v] << endl;
    for(int i = 1; i < lg && par[i - 1][v] != -1; i++)
        par[i][v] = par[i - 1][par[i - 1][v]];
    if(adj[v].empty()){
        l[v] = r[v] = v;
        return;
    }
    l[v] = mod; r[v] = 0;
    for(auto u : adj[v]){
        par[0][u] = v;
        dfs(u);
        l[v] = min(l[v], l[u]);
        r[v] = max(r[v], r[u]);
    }
}

inline int get_sum(int *k, int l, int r){
    return k[r] - (l ? k[l - 1] : 0);
}


int GetBestPosition(int n, int c, int r, int *k, int *s, int *e){

    for(int i = 0; i < n; i++){
        fen::add(i, 1);
        pre[i] = i - 1;
        nxt[i] = i + 1;
        id[i] = i;
        pos[i] = i;
    }
    int newnode = n;
    nxt[n - 1] = -1;
    for(int i = 0; i < c; i++){
        int st = fen::find(s[i] + 1);
        int x = id[st];
        int v = pre[x];
        int z = newnode++;
        id[st] = z;
        pos[z] = st;
        int tt = e[i] - s[i];
        adj[z].pb(x);
        while(tt--){
            x = nxt[x];
            fen::add(pos[x], -1);
            adj[z].pb(x);
        }
        int u = nxt[x];
        if(u != -1)
            pre[u] = z;
        nxt[z] = u;
        if(v != -1)
            nxt[v] = z;
        pre[z] = v;
    }

    int root = newnode - 1;
    memset(par, -1, sizeof par);
    for(int i = 0; i < n - 1; i++){
        k[i] = (k[i] > r);
        if(i)
            k[i] += k[i - 1];
    }
    dfs(root);
    int mx = 0, pos = 0;
    for(int i = 0; i < n; i++){
        int d = 0, v = i;
        for(int j = lg - 1; j >= 0; j--){
            if(par[j][v] != -1 && get_sum(k, l[par[j][v]], ::r[par[j][v]] - 1) == 0){
                v = par[j][v];
                d += (1 << j);
            }
            //cout << "aha " << j << ' ' << v << ' ' << d << endl;
        }
        if(d > mx){
            mx = d;
            pos = i;
        }
        //cout << "hey " << i << ' ' << mx << endl;
    }
    return pos;

}

/*
10 6 3
4 5 6 8 2 9 7 0 1 
2 4
3 5
1 2
3 4
0 2
0 1
*/

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