Submission #767437

#	Time	Username	Problem	Language	Result	Execution time	Memory
767437		mosiashvililuka	Jousting tournament (IOI12_tournament)	C++14	0 / 100	47 ms	16304 KiB

tournament

#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,f[100009],l,r,z,k,za,seg[400009],cnt,msh[200009][20],PI,lst[200009],MX[200009],pas,ANS,val,fx[200009];
vector <int> v[200009];
pair <int, int> P[200009];
set <int> s;
set <int>::iterator it,tt;
void read(int q, int w, int rr){
    if(q==w){
        z=q;
        return;
    }
    if(seg[rr*2]>=k){
        read(q,(q+w)/2,rr*2);
    }else{
        k-=seg[rr*2];
        read((q+w)/2+1,w,rr*2+1);
    }
}
void upd(int q, int w){
    seg[za+q-1]=w;
    q=(za+q-1)/2;
    while(q){
        seg[q]=seg[q*2]+seg[q*2+1];
        q>>=1;
    }
}
void dfsst(int q, int w){
    msh[q][0]=w;
    for(int h=1; h<=18; h++){
        msh[q][h]=msh[msh[q][h-1]][h-1];
    }
    if(q<=a){
        lst[q]=q;
        return;
    }
    for(vector <int>::iterator it=v[q].begin(); it!=v[q].end(); it++){
        dfsst((*it),q);
    }
    for(int h=0; h<v[q].size(); h++){
        if(h+1==v[q].size()){
            lst[q]=lst[v[q][h]];
            MX[q]=max(MX[q],MX[v[q][h]]);
        }else{
            MX[q]=max(MX[q],MX[v[q][h]]);
            MX[q]=max(MX[q],f[lst[v[q][h]]]);
        }
    }
}
int GetBestPosition(int NN, int CC, int RR, int *KK, int *SS, int *EE) {
    a=NN;val=RR;
    for(i=1; i<a; i++){
        f[i]=KK[i-1];
    }
    PI=0;
    for(ii=0; ii<CC; ii++){
        PI++;P[PI]={SS[ii]+1,EE[ii]+1};
    }
    za=1;
    while(za<a) za*=2;
    for(i=1; i<=a; i++){
        s.insert(i);fx[i]=i;
    }
    for(i=1; i<=a; i++){
        seg[za+i-1]=1;
    }
    for(i=za-1; i>=1; i--){
        seg[i]=seg[i*2]+seg[i*2+1];
    }

    cnt=a;
    for(ii=1; ii<=PI; ii++){
        z=0;k=P[ii].first;
        read(1,za,1);
        it=s.lower_bound(z);e=P[ii].second-P[ii].first+1;
        xc=(*it);
        cnt++;
        while(e){
            e--;
            upd((*it),0);
            v[cnt].push_back(fx[(*it)]);
            tt=it;tt++;
            s.erase(it);
            it=tt;
        }
        s.insert(xc);
        upd(xc,1);
        fx[xc]=cnt;
    }

    dfsst(cnt,0);
    ANS=0;
    for(i=1; i<=a; i++){
        pas=0;
        c=i;c=msh[c][0];
        while(c){
            if(MX[c]>val) break;
            pas++;c=msh[c][0];
        }
        ANS=max(ANS,pas);
    }
    return ANS;
}

Compilation message (stderr)

tournament.cpp: In function 'void dfsst(int, int)':
tournament.cpp:40:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for(int h=0; h<v[q].size(); h++){
      |                  ~^~~~~~~~~~~~
tournament.cpp:41:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         if(h+1==v[q].size()){
      |            ~~~^~~~~~~~~~~~~

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