Submission #570982

#	Time	Username	Problem	Language	Result	Execution time	Memory
570982		Deepesson	Jousting tournament (IOI12_tournament)	C++17	100 / 100	928 ms	47152 KiB

tournament

#include <bits/stdc++.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define inbuf_len 1 << 16
#define outbuf_len 1 << 16
#define MAX 505000
#define LSB(A) (A&(-A))

std::vector<int> con[MAX];
int val[MAX];
int cur=32;
int posicao[MAX];
int alocar(void){
    return cur++;
}
typedef std::pair<int,int> pii;
std::vector<int> v;
int contagem=0;
int ft[MAX];
void add(int p,int x){p+=7;
    while(p<MAX){
        ft[p]+=x;
        p+=LSB(p);
    }
}
int get(int p){p+=7;
    int ans=0;
    while(p>0){
        ans+=ft[p];
        p-=LSB(p);
    }
    return ans;
}
int procura(int x){
    if(!x)return 0;
    int l=0,r=MAX;
    while(l<r){
        int m = (l+r)/2;
        int k=get(m);
        if(k<x){
            l=m+1;
        }else r=m;
    }
    return l;
}
void gerar(int l,int r){
    int count=0;
    int alocado = alocar();
    int la=procura(l+1),ra=procura(r+1);
   // std::cout<<"! "<<la<<" "<<ra<<"\n";
    for(int i=la;i<=ra;++i){
      //  std::cout<<i<<" "<<v[i]<<" checando\n";
        if(v[i]==-1){
            continue;
        }
        //std::cout<<v[i]<<" "<<alocado<<"\n";
        con[v[i]].push_back(alocado);
        con[alocado].push_back(v[i]);
        if(i==la)v[i]=alocado;else {v[i]=-1;++contagem;add(i,-1);}
    }
    if(contagem>500){
        memset(ft,0,sizeof(ft));
        contagem=0;
        std::vector<int> novo;
        for(auto&x:v)if(x!=-1)novo.push_back(x);
        for(int i=0;i!=novo.size();++i)add(i,1);
        v=novo;
    }
}
const int inf = 1e9;
pii range[MAX];
int up[MAX][20];
pii dfs(int pos,int prev){
    pii val = {inf,-inf};

    up[pos][0]=prev;
    for(int j=1;j!=20;++j){
        up[pos][j]=up[up[pos][j-1]][j-1];
    }

    if(posicao[pos]){
        int k = posicao[pos]-inf;
        return range[pos]={k,k};
    }

    for(auto&x:con[pos]){
        if(x==prev)continue;
        auto __ = dfs(x,pos);
        val.first=std::min(val.first,__.first);
        val.second=std::max(val.second,__.second);
    }
    return range[pos]=val;
}

int tab[MAX*4];
void update(int t,int k,int la=0,int ra=MAX-1,int pos=1){
    if(la>t||ra<t)return;
    if(la==ra){
        tab[pos]=k;
        return;
    }
    int m = (la+ra)/2;
    update(t,k,la,m,pos*2);
    update(t,k,m+1,ra,(pos*2)+1);
    tab[pos]=std::max(tab[pos*2],tab[(pos*2)+1]);
}

int query(int l,int r,int la=0,int ra=MAX-1,int pos=1){
    if(la>r||ra<l)return -inf;
    if(la>=l&&ra<=r){
        return tab[pos];
    }
    int m = (la+ra)/2;
    return std::max(query(l,r,la,m,pos*2),query(l,r,m+1,ra,(pos*2)+1));
}

int levitar(int pos,int levita){
    for(int j=19;j!=-1;--j){
        if(levita&(1<<j)){
            pos=up[pos][j];
        }
    }
    return pos;
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E){
    ///Primeira etapa: Gerar a arvore
    for(int i=0;i!=N;++i){
        int p = alocar();
        add(i,1);
        v.push_back(p);
        posicao[p] = inf + i;
        if(i){
            update(i,K[i-1]);
        }else update(0,R);
    }
    for(int i=0;i!=C;++i){
        gerar(S[i],E[i]);
    }
    range[0]={-inf,-inf};
    int raiz = cur-1;
    dfs(raiz,-1);

    int best=0,pos=0;
    for(int i=0;i!=N;++i){
        int l=0,r=C;
        while(l<r){
            int m = (l+r+1)/2;
            int posicao = levitar(32+i,m);
            int valor = query(range[posicao].first,range[posicao].second);
          //  std::cout<<m<<" "<<posicao<<" "<<valor<<" "<<32+i<<" "<<range[posicao].first<<" "<<range[posicao].second<<"\n";
            if(valor==R){
                l=m;
            }else r=m-1;
        }

        if(l>best){
               // std::cout<<"show!\n";
            best=l;
            pos=i;
        }

        if(i!=N-1){
            update(i,K[i]);
            update(i+1,R);
        }
    }

    return pos;
}

Compilation message (stderr)

tournament.cpp: In function 'void gerar(int, int)':
tournament.cpp:68:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         for(int i=0;i!=novo.size();++i)add(i,1);
      |                     ~^~~~~~~~~~~~~
tournament.cpp:49:9: warning: unused variable 'count' [-Wunused-variable]
   49 |     int count=0;
      |         ^~~~~

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