Submission #1045184

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045184		tosivanmak	Jousting tournament (IOI12_tournament)	C++17	100 / 100	57 ms	48416 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){
    // cout<<s<<" "<<l[s]<<" "<<r[s]<<'\n';
    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;
        // cout<<s<<" "<<rounds<<" "<<nd<<'\n';
        if(rounds>maxi){maxi=rounds,corre=nd;}
        else if(rounds==maxi){corre=min(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[ancnode[poss[0]]];
        r[ass]=r[ancnode[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;
}

/*
#define inbuf_len 1 << 16
#define outbuf_len 1 << 16

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E);

int main() {
  int tmp;


  char *inbuf, *outbuf;
  inbuf = (char*) malloc(inbuf_len * sizeof(char));
  outbuf = (char*) malloc(outbuf_len * sizeof(char));
  tmp = setvbuf(stdin, inbuf, _IOFBF, inbuf_len);
  assert(tmp == 0);
  tmp = setvbuf(stdout, outbuf, _IOFBF, outbuf_len);
  assert(tmp == 0);

  int N, C, R;
  int *K, *S, *E;
  tmp = scanf("%d %d %d", &N, &C, &R);
  assert(tmp == 3);
  K = (int*) malloc((N-1) * sizeof(int));
  S = (int*) malloc(C * sizeof(int));
  E = (int*) malloc(C * sizeof(int));
  int i;
  for (i = 0; i < N-1; i++) {
    tmp = scanf("%d", &K[i]);
    assert(tmp == 1);
  }
  for (i = 0; i < C; i++) {
    tmp = scanf("%d %d", &S[i], &E[i]);
    assert(tmp == 2);
  }

  printf("%d\n", GetBestPosition(N, C, R, K, S, E));

  return 0;

}
*/

Compilation message (stderr)

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

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