Submission #570977

#	Time	Username	Problem	Language	Result	Execution time	Memory
570977		Deepesson	Jousting tournament (IOI12_tournament)	C++17	49 / 100	1088 ms	15196 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

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;
void gerar(int l,int r){
    int count=0;
    int alocado = alocar();
    for(int i=0;i!=v.size();++i){
        if(v[i]==-1){
            continue;
        }
        if(count>=l&&count<=r){
            con[v[i]].push_back(alocado);
            con[alocado].push_back(v[i]);
            if(count==l)v[i]=alocado;else {v[i]=-1;++contagem;}
        }
        ++count;
    }
    if(contagem>350){
        contagem=0;
        std::vector<int> novo;
        for(auto&x:v)if(x!=-1)novo.push_back(x);
        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];
           // std::cout<<up[pos][j]<<"\n";
        }
    }
    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();
        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:23:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for(int i=0;i!=v.size();++i){
      |                 ~^~~~~~~~~~

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