oj.uz

Submission #570982

# Submission time Handle Problem Language Result Execution time Memory
570982 2022-05-31T22:50:58 Z Deepesson Jousting tournament (IOI12_tournament) C++17
100 / 100
 928 ms 47152 KB 
#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

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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12244 KB Output is correct
2 Correct 8 ms 12244 KB Output is correct
3 Correct 8 ms 12372 KB Output is correct
4 Correct 8 ms 12372 KB Output is correct
5 Correct 8 ms 12252 KB Output is correct
6 Correct 9 ms 12308 KB Output is correct
7 Correct 9 ms 12372 KB Output is correct
8 Correct 10 ms 12312 KB Output is correct
9 Correct 8 ms 12244 KB Output is correct
10 Correct 10 ms 12244 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14420 KB Output is correct
2 Correct 32 ms 15828 KB Output is correct
3 Correct 16 ms 14872 KB Output is correct
4 Correct 26 ms 15572 KB Output is correct
5 Correct 33 ms 15564 KB Output is correct
6 Correct 20 ms 15188 KB Output is correct
7 Correct 31 ms 15700 KB Output is correct
8 Correct 31 ms 15608 KB Output is correct
9 Correct 15 ms 14804 KB Output is correct
10 Correct 23 ms 15512 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 25148 KB Output is correct
2 Correct 928 ms 47152 KB Output is correct
3 Correct 255 ms 29712 KB Output is correct
4 Correct 821 ms 44376 KB Output is correct
5 Correct 873 ms 44936 KB Output is correct
6 Correct 568 ms 37204 KB Output is correct
7 Correct 896 ms 45960 KB Output is correct
8 Correct 835 ms 45956 KB Output is correct
9 Correct 163 ms 28868 KB Output is correct
10 Correct 430 ms 29792 KB Output is correct