Submission #1037928

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037928		idas	Jousting tournament (IOI12_tournament)	C++11	100 / 100	167 ms	17912 KiB

tournament

#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin); i<(end); i++)
#define pb push_back
#define s second
#define f first

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;

const int MxN=1e5+10, INF=1e9;
int n, Rank, Start[MxN], s[MxN], e[MxN], fen[MxN], t[4*MxN], mx[MxN];
vi ad[MxN];

void upd(int p, int x)
{
    for(int i=p; i<MxN; i+=i&(-i)) fen[i]+=x;
}

int get(int p)
{
    int ret=0;
    for(int i=p; i>0; i-=i&(-i)) ret+=fen[i];
    return ret;
}

int get_lin(int x)
{
    int l=1, r=n;
    while(l<r){
        int m=(l+r)/2;
        if(get(m)<x) l=m+1;
        else r=m;
    }
    return l;
}

int get_rin(int x)
{
    int l=1, r=n;
    while(l<r){
        int m=(l+r+1)/2;
        if(get(m)>x) r=m-1;
        else l=m;
    }
    return l;
}

void upd_max(int p, int x, int l=1, int r=n, int id=1)
{
    if(l==r){
        t[id]=x;
        return;
    }
    int m=(l+r)/2;
    if(p<=m) upd_max(p, x, l, m, id*2);
    else upd_max(p, x, m+1, r, id*2+1);
    t[id]=max(t[id*2], t[id*2+1]);
}

int get_max(int x, int y, int l=1, int r=n, int id=1)
{
    if(r<x||l>y) return -1;
    if(x<=l&&r<=y) return t[id];
    int m=(l+r)/2;
    return max(
        get_max(x, y, l, m, id*2),
        get_max(x, y, m+1, r, id*2+1)
    );
}

int ans, max_wins;
void dfs(int u, int wins=0)
{
//    cout << u << " " << wins << endl;
    if(int(ad[u].size())==0 && mx[u]==Rank){
        wins++;
        if(wins>max_wins){
            max_wins=wins;
            ans=Start[u];
        }
    }

    for(auto it : ad[u]){
        if(mx[u]==Rank) dfs(it, wins+1);
        else dfs(it, 0);
    }
}

int GetBestPosition(int N, int c, int r, int *k, int *S, int *E) {
    n=N; Rank=r; FOR(i, 0, c) s[i]=S[i], e[i]=E[i];
    set<pii> st;
    FOR(i, 1, n+1) upd(i, 1), st.insert({i,-1});
    FOR(i, 1, n)
    {
        upd_max(i, k[i-1]);
    }

    FOR(i, 0, c)
    {
        int l_in=get_lin(s[i]+1), r_in=get_rin(e[i]+1);
        mx[i]=max(get_max(l_in, r_in-1), r);

//        cout << i << ": " << l_in << " " << r_in << " -> " << mx[i] << '\n';

        vector<pii> er;
        auto it=st.lower_bound({l_in,-1});
        while(it!=st.end() && (*it).f<=r_in){
            er.pb(*it);
            int pos=(*it).f, in=(*it).s;
            if(in!=-1) ad[i].pb(in);
            upd(pos, -1);
            it++;
        }

        for(auto iter : er) st.erase(iter);

        st.insert({l_in,i});
        Start[i]=l_in-1;
        upd(l_in, 1);

//        cout << i << ": ";
//        for(auto iter : ad[i]) cout << iter << " ";
//        cout << '\n';
    }

    dfs(c-1);

//    cout << "wins: " << max_wins << endl;

    return ans;
}

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