Submission #1045169

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045169		tosivanmak	Jousting tournament (IOI12_tournament)	C++17	0 / 100	26 ms	32080 KiB

tournament

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

struct node{
  ll dep,id;
    bool operator<(const node& n)const{
        if(dep!=n.dep)return dep<n.dep;
        return id>n.id;
    }
};
struct SEG{
  ll seg[400005],n;
    void init(ll _n){
        n=_n;
    }
    void build(ll l, ll r, ll id){
        if(l==r){
            seg[id]=1; return;
        }
        ll mid=(l+r)>>1;
        build(l,mid,id*2),build(mid+1,r,id*2+1);seg[id]=seg[id*2]+seg[id*2+1];
    }
    void del(ll ul, ll l, ll r, ll id){
        seg[id]--;
        if(l==r){return;}
        ll mid=(l+r)>>1;
        if(ul<=mid)del(ul,l,mid,id*2);
        else del(ul,mid+1,r,id*2+1);
    }
    ll bs(ll k, ll l, ll r, ll id){
        if(l==r)return l;
        ll mid=(l+r)>>1;
        if(seg[id*2]>=k)return bs(k,l,mid,id*2);
        else return bs(k-seg[id*2],mid+1,r,id*2+1);
    }
    ll pos(ll k){
        return bs(k,1,n,1);
    }
}finds;

ll ancnode[400005],fa[400005],ass=100001,l[400005],r[400005],dep[400005];set<ll>st;
vector<ll>adj[400005];
node maxdep[400005];
ll maxi=-1,corre=-1;
void dfs(ll s){
    if(l[s]==r[s])maxdep[s]={dep[s],l[s]};
    else maxdep[s]={-1,-1};
    for(auto& u: adj[s]){
        dep[u]=dep[s]+1;
        dfs(u);
        maxdep[s]=max(maxdep[s],maxdep[u]);
    }
    ll bruh=*st.lower_bound(l[s]);
    if(bruh>=r[s]){
        ll rounds=maxdep[s].dep-dep[s],nd=maxdep[s].id;
        if(rounds>maxi){maxi=rounds,corre=nd;}
        else if(rounds==maxi){corre=max(corre,nd);}
    }
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
    finds.init(N);finds.build(1,N,1);
    for(int i=1;i<=N;i++)ancnode[i]=i,l[i]=i,r[i]=i;
    for(int i=0;i<C;i++){
        S[i]++,E[i]++;    
    }
    for(int i=0;i<N-1;i++){
        if(K[i]>R)st.insert(i+1);
    }
    st.insert(1e18);
    for(int i=0;i<C;i++){
        vector<ll>poss;
        for(int j=S[i];j<=E[i];j++){
            poss.push_back(finds.pos(j));
        }
        for(int j=0;j<poss.size();j++){
            fa[ancnode[poss[j]]]=ass;
            adj[ass].push_back(ancnode[poss[j]]);
        }
        l[ass]=l[poss[0]];
        r[ass]=r[poss[poss.size()-1]];
        ass++;
        ancnode[poss[0]]=ass-1;
        for(int j=1;j<poss.size();j++)finds.del(poss[j],1,N,1);
    }
    ass--; dep[ass]=0;
    dfs(ass);
    return corre-1;
}

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:76:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         for(int j=0;j<poss.size();j++){
      |                     ~^~~~~~~~~~~~
tournament.cpp:84:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |         for(int j=1;j<poss.size();j++)finds.del(poss[j],1,N,1);
      |                     ~^~~~~~~~~~~~

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