Submission #242362

#	Time	Username	Problem	Language	Result	Execution time	Memory
242362		tqbfjotld	Jousting tournament (IOI12_tournament)	C++14	100 / 100	342 ms	36856 KiB

tournament

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;

pair<int,int> actual[100005];

bool cmp(pair<int,int> a, pair<int,int> b){
    if (a.first==b.first) return a.second>b.second;
    return a.first<b.first;
}
vector<int> adjl[100005];
int ranks[100005];
int k;

struct nd{
    int s,e,v;
    nd *l,*r;
    nd(int _s, int _e){
        s = _s;
        e = _e;
        if (s==e){
            v = ranks[s];
        }
        else{
            l = new nd(s,(s+e)/2);
            r = new nd((s+e)/2+1,e);
            v = max(l->v,r->v);
            //printf("v %d %d = %d\n",s,e,v);
        }
    }
    int query(int a, int b){
        if (a<=s && e<=b) return v;
        if (b<=(s+e)/2) return l->query(a,b);
        if (a>(s+e)/2) return r->query(a,b);
        return max(l->query(a,b),r->query(a,b));
    }
}*root;

pair<int,int> dfs(int node, int dist){
    int mx = root->query(actual[node].first,actual[node].second-1);
    //printf("querying %d %d\n",actual[node].first,actual[node].second-1);
    //printf("node %d, mx %d\n",node,mx);
    if (mx>k){
        dist = 0;
    }
    int nd = -1;
    pair<int,int> ans = {-1,-1};
    int r = actual[node].first-1;
    for (auto x : adjl[node]){
        if (nd==-1 && actual[x].first>r+1){
            nd = r+1;
        }
        auto res = dfs(x,dist+1);
        if (res.first>ans.first || (res.first==ans.first && res.second<ans.second)){
            ans = res;
        }
    }
    if (nd==-1 && r<actual[node].second){
        nd = r+1;
    }
    if (nd!=-1){
        if (dist>ans.first || (ans.first==dist && nd<ans.second)){
            ans = {dist,nd};
        }
    }
    return ans;
}



using namespace __gnu_pbds;
typedef tree<long long, null_type, less<long long>,rb_tree_tag, tree_order_statistics_node_update> indexed_set;

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
    k = R;
    for (int x = 0; x<N-1; x++){
        ranks[x] = K[x];
        //printf("ranks %d = %d\n",x,K[x]);
    }
    root = new nd(0,N-2);
    indexed_set pb;
    for (int x = 0; x<=2*N; x++){
        pb.insert(x);
    }
    //printf("%d\n",root->query(0,1));
    for (int x = 0; x<C; x++){
        actual[x] = {*pb.find_by_order(S[x]),*pb.find_by_order(E[x]+1)-1};
        auto en = pb.find_by_order(E[x]+1);
        for (auto it = pb.find_by_order(S[x]+1); ; ){

            if ((*it)==actual[x].second+1) break;
            it = pb.erase(it);
        }
        assert(actual[x].second<N);
    }
    sort(actual,actual+C,cmp);
    //return 0;
    assert(actual[0]==make_pair(0,N-1));
    stack<int> st;
    st.push(0);
    for (int x = 1; x<C; x++){
        while (actual[x].second>actual[st.top()].second){
            assert(!st.empty());
            st.pop();
        }
        if (actual[x].second<=actual[st.top()].second){
            adjl[st.top()].push_back(x);
            st.push(x);
        }
    }

    return dfs(0,R==N-1?1:0).second;

}

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:89:14: warning: variable 'en' set but not used [-Wunused-but-set-variable]
         auto en = pb.find_by_order(E[x]+1);
              ^~

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