Classifica senza fili

Aiuto
1

Salve, sto da un po’ di tempo su questo esercizio e non mi spiego come mai il mio codice non risolva i casi di esempio che in locale svolge correttamente.
Svolge correttamente anche alcuni testcase che ho realizzato per testare ogni richiesta.
L’ idea che ho addotato è di usare un segment tree per eseguire Squalifica e Partecipante in O(log(N)) mentre la funzione supera in O(1).
Utilizzo una lista per tenermi salvato la classifica, e quando elimino un partecipante collego l’ elemento precedente con il successivo.
Il segment lo utilizzo per sapere quale posizione è effettivamente occuputa da un partecipante ancora in gara. Quando elimino un partecipante azzero la posizone da lui occupata modificando il numero di giocatori presenti nei range che coinvolge.
Per la funzione partecipante se il numero del partecipante che cerco è minore o uguale al valore del range del nodo sinistro, visto il nodo sinistro; altrimenti visito il nodo destro diminuendo la posizone che cerco del numero di giocatori presenti nel nodo sinistro.
code:

#include <bits/stdc++.h>
#define MAXN 1000001

using namespace std;

struct classifica{
	int id = 0,left = 0,right = 0;
};

classifica C[MAXN];
int tree[MAXN * 4];

class st{
	public :
		st(int N,int *tree){
			this->S = N;
			this->tree = tree;
			build(0,0,S - 1);
		}
		void update(int index){
			this->pos = index;
			updateUtil(0,0,S - 1);
		}
		int query(int index){
			this->pos = index;
			queryUtil(0,0,S - 1);
		}
	;
	private :
		int S,*tree = NULL;
		// utilities
		inline int RC(int &i){
			return i * 2 + 2;
		}
		inline int LC(int &i){
			return i * 2 + 1;
		}
		inline int get_mid(int s,int e){
			return (s + e) / 2;
		}
		// builder
		void build(int node,int s,int e){
			if(s == e){
				tree[node] = 1;
			}else{
				int rc = RC(node);
				int lc = LC(node);
				int mid = get_mid(s,e);
				build(lc,s,mid);
				build(rc,mid + 1,e);
				tree[node] = tree[rc] + tree[lc];
			}
		}
		// query and update
		int pos;
		void updateUtil(int node,int s,int e){
			if(s > pos || e < pos)return;
			if(s == pos && e == pos){
				tree[node] = 0;
				return;
			}
			int lc = LC(node);
			int rc = RC(node);
			int mid = get_mid(s,e);
			updateUtil(lc,s,mid);
			updateUtil(rc,mid + 1,e);
			tree[node] = tree[lc] + tree[rc];
		}
		
		int queryUtil(int node,int s,int e){
			if(s == e){
				return s;
			}
			int lc = LC(node);
			int rc = RC(node);
			int mid = get_mid(s,e);
			if(tree[lc] < pos){
				pos -= tree[lc];
				return queryUtil(rc,mid + 1,e);
			}else{
				return queryUtil(lc,s,mid);
			}
		}	
	;
};

int posizioni[MAXN];

st *T = NULL;
void inizia(int N, int ids[]){
	for(int i = 0; i < N; i++){
		C[i].id = ids[i];
		C[i].left = i - 1;
		C[i].right = i + 1;
		posizioni[ids[i]] = i;
	}
	T = new st(N,tree);
}

void supera(int id){
	int p1 = posizioni[id];
	int p2 = C[p1].left;
	int id2 = C[p2].id;
	swap(C[p1].id,C[p2].id);
	swap(posizioni[id],posizioni[id2]);	
};

/*
	rip  b 
	<-A-><-b-><-c-><-d->
	<-A-><-c-><-d->
*/

void squalifica(int id){
	int p1 = posizioni[id];
	int left = C[p1].left;
	int right = C[p1].right;
	C[left].right = right;
	C[right].left = left;
	T->update(p1);
}

int partecipante(int pos){
	pos = T->query(pos);
	return C[pos].id;
}
2

Ti rispondo ben volentieri ho provato la tua ed ho fatto 100/100 al primo colpo.
P.S.
Correzioni apportate:
la funzione

int query(int index){
this->pos = index;
queryUtil(0,0,S - 1);
}

deve restituire un valore e quindi ho corretto la terza riga con:

return queryUtil(0,0,S - 1);

poi ho tolto le inizializzazioni in

struct classifica{
int id = 0,left = 0,right = 0;
};
e
int S,*tree = NULL;

(al mio compilatore non piacevano) e sono quindi diventate:

struct classifica{
int id ,left ,right ;
};
int S,*tree ;

Probabilmente il compilatore della piattaforma le accetta e quindi non era necessario toglierle.

2 Mi Piace
3

Come ho fatto a non vederlo… grazie!

No, non era neccessario toglierle.

4

Quella sintassi viene accettata dalla versione C++11 del linguaggio, pare che la “feature” si chiami brace-or-equals initializer, perché al posto dell’uguale si possono anche usare le parentesi graffe, tipo così:

struct a {
	int x = 3;
};

struct b {
	int x{3};
};
1 Mi Piace
5

Avevo usato una vecchia versione del compilatore C++ quella più nuova non fa storie.!