Submission #122057

#	Time	Username	Problem	Language	Result	Execution time	Memory
122057		Osama_Alkhodairy	Jousting tournament (IOI12_tournament)	C++17	0 / 100	208 ms	33100 KiB

tournament

#include <bits/stdc++.h>
//~ #include "grader.cpp"
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree <pair <int, int>, null_type, less <pair <int, int> >, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int N = 1000001;

int n, c, r, mxd[N], can[N], d[N], sum[N], rightmost[N];
vector <int> v[N];
ordered_set invs;
map <pair <int, int>, int> mp;

int id(pair <int, int> p){
    if(mp.find(p) == mp.end()){
        int sz = mp.size();
        mp[p] = sz;
    }
    return mp[p];
}
void dfs(int node, int pnode, int dep){
    mxd[node] = d[node] = dep;
    if(v[node].size() == 0){
        can[node] = 1;
        return;
    }
    for(auto &i : v[node]){
        dfs(i, node, dep + 1);
        mxd[node] = max(mxd[node], mxd[i]);
        sum[node] += sum[i];
    }
    if(sum[node] == 0) can[node] = 1;
    if(sum[node] == 1 && rightmost[v[node].back()]){
        can[node] = 1;
        rightmost[node] = 1;
    }
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E){
    n = N;
    c = C;
    r = R;
    for(int i = 0 ; i < n ; i++){
        invs.insert({i, i});
        id({i, i});
    }
    for(int i = 0 ; i < c ; i++){
        int l = S[i], r = E[i];
        assert(r < (int)invs.size());
        vector <pair <int, int> > children;
        for(int j = 0 ; j < r - l + 1 ; j++){
            auto it = invs.find_by_order(l);
            children.push_back(*it);
            invs.erase(it);
        }
        l = children[0].first;
        r = children.back().second;
        for(auto &i : children){
            v[id({l, r})].push_back(id(i));
        }
        invs.insert({l, r});
    }
    for(int i = 0 ; i < n - 1 ; i++){
        if(K[i] > R){
            sum[id({i, i})] = rightmost[id({i, i})] = 1;
        }
    }
    int root = id({0, n - 1});
    dfs(root, -1, 0);
    int ans = 0;
    for(int node = 0 ; node < (int)mp.size() ; node++){
        if(can[node]){
            ans = max(ans, mxd[node] - d[node]);
        }
    }
    return ans;
}

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