Submission #587105

#	Time	Username	Problem	Language	Result	Execution time	Memory
587105		mosiashvililuka	Jousting tournament (IOI12_tournament)	C++14	100 / 100	229 ms	28620 KiB

tournament

#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,tes,t,R,f[100009],seg[400009],seg2[400009],l,r,z,za,Z,msh[400009],cnt,mx[400009],ans[400009],LE[400009],RI[400009],SEG[400009];
vector <int> v[400009];
set <pair <int, int> > s;
set <pair <int, int> >::iterator it,tt;
void READ(int q, int w, int rr){
    if(q>r||w<l) return;
    if(q>=l&&w<=r){
        z=max(z,SEG[rr]);
        return;
    }
    READ(q,(q+w)/2,rr*2);
    READ((q+w)/2+1,w,rr*2+1);
}
void pushdown(int q, int w, int rr){
    if(q!=w){
        seg2[rr*2]+=seg2[rr];
        seg2[rr*2+1]+=seg2[rr];
    }
    seg[rr]+=seg2[rr];
    seg2[rr]=0;
}
void upd(int q, int w, int rr){
    pushdown(q,w,rr);
    if(q>r||w<l) return;
    if(q>=l&&w<=r){
        seg2[rr]=z;
        pushdown(q,w,rr);
        return;
    }
    upd(q,(q+w)/2,rr*2);
    upd((q+w)/2+1,w,rr*2+1);
    seg[rr]=max(seg[rr*2],seg[rr*2+1]);
}
void read(int q, int w, int rr){
    if(q==w){
        z=q;
        return;
    }
    pushdown(q,(q+w)/2,rr*2);
    pushdown((q+w)/2+1,w,rr*2+1);
    if(seg[rr*2]<Z){
        read((q+w)/2+1,w,rr*2+1);
    }else{
        read(q,(q+w)/2,rr*2);
    }
}
void dfs(int q, int w){
    l=LE[q];r=RI[q]-1;z=0;
    if(l<=r){
        READ(1,za,1);
        mx[q]=z;
    }
    if(q<=a){
        //mx[q]=f[q];
        return;
    }
    for(vector <int>::iterator it=v[q].begin(); it!=v[q].end(); it++){
        if((*it)==w) continue;
        dfs((*it),q);
        //mx[q]=max(mx[q],mx[(*it)]);
    }
}
void dfs2(int q, int w, int rr){
    if(q<=a){
        ans[q]=rr-1;
        return;
    }
    if(mx[q]>R) rr=0;
    for(vector <int>::iterator it=v[q].begin(); it!=v[q].end(); it++){
        if((*it)==w) continue;
        dfs2((*it),q,rr+1);
    }
}
int GetBestPosition(int NN, int CC, int RR, int *KK, int *SS, int *EE) {
    a=NN;tes=CC;R=RR;R++;
    for(i=1; i<a; i++){
        f[i]=KK[i-/*2*/1];f[i]++;
    }
    za=1;
    while(za<a) za*=2;
    for(i=1; i<a; i++){
        SEG[za+i-1]=f[i];
    }
    for(i=za-1; i>=1; i--){
        SEG[i]=max(SEG[i*2],SEG[i*2+1]);
    }
    for(i=1; i<=a; i++){
        s.insert({i,i});
        l=i;r=za;z=1;
        upd(1,za,1);
    }
    cnt=a;
    for(i=1; i<=a; i++){
        LE[i]=RI[i]=i;
    }
    for(t=1; t<=tes; t++){
        c=SS[t-1]+1;d=EE[t-1]+1;
        Z=c;z=0;
        pushdown(1,za,1);
        read(1,za,1);
        e=z;
        //cout<<"tes: "<<t<<"   "<<e<<"\n";
        //if(t==3) return 0;
        it=s.lower_bound({e,0});
        zx=d-c+1;cnt++;
        LE[cnt]=LE[(*it).second];RI[cnt]=RI[(*it).second];
        while(zx>0){
            zx--;
            msh[(*it).second]=cnt;
            v[cnt].push_back((*it).second);
            l=(*it).first;r=za;z=-1;
            upd(1,za,1);
            tt=it;tt++;
            RI[cnt]=RI[(*it).second];
            s.erase(it);
            it=tt;
        }
        s.insert({e,cnt});
        l=e;r=za;z=1;
        upd(1,za,1);
    }
    /*for(i=1; i<=cnt; i++){
        cout<<i<<" "<<msh[i]<<"\n";
    }
    for(i=1; i<=a; i++) cout<<f[i]<<" ";
    cout<<"\n";*/
    dfs(cnt,0);
    dfs2(cnt,0,1);
    zx=-1;xc=0;
    for(i=1; i<=a; i++){
        //zx=max(zx,ans[i]);
        if(zx<ans[i]){
            zx=ans[i];xc=i;
        }
    }
    return xc-1;
}

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