Estuve tratando de resolver este problema. Cuando lo envío al juez me da 0 puntos por wrong answer en todos los casos, pero no encuentro el problema con mi solución. Capaz no sea la mejor o más limpia, pero me gustaría arreglarla. La dejo acá abajo por si alguien me puede dar una mano. Gracias!
Mi código
#define forn(i,N) for (int i=0;i<N;i++)
#define rforn(i,N) for(int i=N;i>0;i--)
struct persona
{
int pos, enojo;
bool operator<(const persona other) const
{
if ( enojo < other.enojo )
return true;
if ( enojo == other.enojo )
return pos > other.pos;
return false;
}
};
struct Fecha
{
int dia, mes, anno;
};
const int maxN = 1<<18;
int N;
int segTree[600000];
int positions[600000];
priority_queue <persona> personas;
int findMin( int left, int right, int lsearch, int rsearch , int node ){
if ( left > rsearch || right < lsearch)
return -1;
if (left>=lsearch && right <= rsearch){
return node;
}
int lres = findMin ( left , (left+right)/2 , lsearch , rsearch , node*2 );
int rres = findMin ( (left+right)/2 + 1 , right , lsearch , rsearch , node*2+1 );
if (lres > -1 && rres > -1){
if (segTree[lres] >= segTree[rres]){
return rres;
}else{
return lres;
}
}
if (lres > -1)
return lres;
if (rres > -1)
return rres;
return -1;
}
int fila(vector<Fecha> orden, vector<int> &enojados)
{
int maxEnojo = -maxN*2;
/// setea todo a infinito
forn(i,maxN*2){
segTree[i]=maxN*2;
}
/// calcula la edad de cada uno
forn(i,N){
segTree[i+maxN] = (10000 - orden[i].anno)*10000 + (12-orden[i].mes)*100 + (31 - orden[i].dia);
positions[i+maxN] = i+1;
}
/// calcula los nodos internos del segment tree
rforn(i,maxN-1){
if(segTree[2*i] < segTree[2*i+1]){
segTree[i] = segTree[2*i];
positions [i] = positions[2*i];
} else {
segTree[i] = segTree[2*i+1];
positions [i] = positions[2*i+1];
}
}
/// calcula el enojo de cada persona
forn(i,N){
int enojo = 0;
int masChico = positions[ findMin( 1 , maxN , 1 , i+1, 1) ]-1;
enojo = i-masChico;
if (segTree[masChico+maxN] >= segTree[i+maxN])
continue;
forn(j,masChico){
if ( segTree[j+maxN] < segTree[i+maxN]){
enojo = i-j;
break;
}
}
personas.push({i+1,enojo});
maxEnojo = max(enojo,maxEnojo);
}
while ( !personas.empty() ){
enojados.push_back(personas.top().pos);
personas.pop();
}
return maxEnojo;
}