Submission #1034648

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034648		idas	Jousting tournament (IOI12_tournament)	C++11	0 / 100	23 ms	10076 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, rnk, strt[MxN], mx[MxN], t[4*MxN], a[MxN];
bool bad[MxN];
vi ad[MxN];

void build(int l=0, int r=n-1, int id=1)
{
    if(l==r){
        t[id]=a[l];
        return;
    }
    int m=(l+r)/2;
    build(l, m, id*2);
    build(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=0, int r=n-1, 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 max_ans, ans=INF;
void dfs(int u, int max_depth=0)
{
//    cout << u << ": " << max_depth << '\n';

    bool badd=false;
    if(mx[u]!=rnk) badd=true;

    if(max_depth+1>max_ans){
        max_ans=max_depth+1;
        ans=strt[u];
    }

    for(auto it : ad[u]){
        dfs(it, max_depth+!badd);
    }
}

int GetBestPosition(int N, int c, int r, int *k, int *s, int *e) {
    FOR(i, 0, c) strt[i]=s[i];
    n=N; rnk=r;
    int add=0;
    set<pii> st;
    FOR(i, 0, c)
    {
        vector<pii> er;
        auto it=st.lower_bound({s[i],0});
        while(it!=st.end() && (*it).f<=e[i]){
            ad[i].pb((*it).s);
            bad[(*it).s]=true;
            er.pb(*it);
            it++;
        }

        for(auto iter : er) st.erase(iter);
        st.insert({s[i],i});

        int to_add=e[i]-s[i];
        e[i]+=add;
        add+=to_add;
    }

    FOR(i, 0, n-1) a[i]=k[i];

    build();

    int start_node=-1;
    FOR(i, 0, c)
    {
        mx[i]=max(get_max(s[i], e[i]-1), r);

        if(!bad[i]){
            assert(start_node==-1);
            start_node=i;
        }
    }

    dfs(start_node);

    return (ans==INF?0:ans);
}

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