Submission #583673

#	Time	Username	Problem	Language	Result	Execution time	Memory
583673		hibiki	Jousting tournament (IOI12_tournament)	C++11	0 / 100	81 ms	12212 KiB

tournament

#include<bits/stdc++.h>
using namespace std;

#define pb push_back
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T> using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int n,c,r,ans, k[100005];
int t_idx[100005], cnt, root;
pair<int,int> ran[200005];
vector<int> v[200005];

struct node
{
    int mx;
    node *l, *r;
} *seg;

node* build(int l, int r)
{
    node *ptr = new node;
    if(l == r)
    {
        ptr->mx = k[l];
        return ptr;
    }
    int mid = (l + r) / 2;
    ptr->l = build(l,mid);
    ptr->r = build(mid + 1, r);
    ptr->mx = max(ptr->l->mx, ptr->r->mx);
    return ptr;
}

int ll,rr;
int query(node *ptr,int l,int r)
{
    if(ll <= l && r <= rr) return ptr->mx;
    if(r < ll || rr < l) return 0;
    int mid = (l + r) / 2;
    return max(query(ptr->l,l,mid), query(ptr->r,mid + 1,r));
}

int dfs(int nw)
{
    int ret = 0;
    for(auto go: v[nw])
        ret = max(ret, dfs(go));
    if(nw > n)
    {
        ll = ran[nw].f;
        rr = ran[nw].s - 1;
        if(query(seg, 0, n - 1) < r)
            ans = max(ans, ret);
    }
    return ret + 1;
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E)
{
    n = N, c = C, r = R, ans = 0;
    indexed_set<int> os;
    for(int i = 0; i < n; i++)
        k[i] = K[i];
    seg = build(0, n - 1);
    for(int i = 0; i <= n; i++)
    {
        os.insert(i);
        t_idx[i] = i;
    }
    cnt  = n + 1;
    for(int i = 0; i < c; i++)
    {
        int st = *os.find_by_order(S[i]);
        int ed = *os.find_by_order(E[i] + 1) - 1;

        v[cnt].pb(t_idx[st]);
        for(int j = S[i] + 1; j <= E[i]; j++)
        {
            int cur = *os.find_by_order(S[i] + 1);
            v[cnt].pb(t_idx[cur]);
            os.erase(cur);
        }
        t_idx[st] = cnt;

        ran[cnt] = {st,ed};
        S[i] = st, E[i] = ed;
        cnt++;
    }
    root = cnt - 1;
    dfs(root);
    return ans;
}

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