oj.uz

Submission #1034646

# Submission time Handle Problem Language Result Execution time Memory
1034646 2024-07-25T15:47:36 Z idas Jousting tournament (IOI12_tournament) C++11
0 / 100
 21 ms 10588 KB 
#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)
{
    bool badd=false;
    if(mx[u]!=rnk) badd=true;

    if(max_depth>max_ans){
        max_ans=max_depth;
        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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 5468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Runtime error 21 ms 10588 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -