Submission #242226

#	Time	Username	Problem	Language	Result	Execution time	Memory
242226		tqbfjotld	Jousting tournament (IOI12_tournament)	C++14	0 / 100	34 ms	16632 KiB

tournament

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

pair<int,int> actual[100005];
int fenwick[100005];
int qu(int p){
    p++;
    int ans = 0;
    while (p>0){
        ans += fenwick[p];
        p-= (p&-p);
    }
    return ans;
}
void upd(int p, int v){
    p++;
    while (p<100005){
        fenwick[p] += v;
        p += (p&-p);
    }
}

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;
}

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);
    //printf("%d\n",root->query(0,1));
    for (int x = 0; x<C; x++){
        actual[x] = {qu(S[x]-1)+S[x],qu(E[x])+E[x]};
        int offsetE = qu(E[x]);
        upd(S[x],E[x]-S[x]+offsetE);
        upd(E[x],offsetE+E[x]-S[x]-qu(E[x]));
        assert(actual[x].second<N);
    }
    sort(actual,actual+C,cmp);
    for (int x = 0; x<C; x++){
        //printf("%d %d\n",actual[x].first,actual[x].second);
    }
    //return 0;
    assert(actual[0]==make_pair(0,N-1));
    stack<int> st;
    st.push(0);
    for (int x = 1; x<C; x++){
        if (actual[x].second<=actual[st.top()].second){
            adjl[st.top()].push_back(x);
            st.push(x);
        }
        else{
            st.pop();
        }
    }


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

}

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