Hola! Me puse a resolver el problema “DQUERY” del 5to envío. Quería ver si alguien me daba una mano optimizando mi solución, porque SPOJ me devuelve TLE y no puedo saber qué puntaje saqué.
Dejo mi código y explico un poco lo que hice:
Código
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>
#define forn(i,N) for(int i=0;i<N;i++)
using namespace std;
struct query {
int a, b, ini, res;
};
int N, M, Q; /// N numbers, M bucket size, Q queries
int sequence[40000];
vector <query> queries;
map <int,int> elements;
bool byPos(query x, query y){
return x.ini < y.ini;
}
bool moSort(query x, query y){
if (x.a/M < y.a/M){
return true;
}
if (x.a/M == y.a/M){
if (x.b < y.b){
return true;
} else {
return false;
}
}
return false;
}
void addElement(int pos){
if (elements.count(sequence[pos])){
elements[ sequence[pos] ] += 1;
} else {
elements[ sequence[pos] ] = 1;
}
}
void removeElement(int pos){
elements[ sequence[pos] ] -= 1;
if (!elements[sequence[pos]]){
elements.erase(sequence[pos]);
}
}
void processQueries(){
int x=1, y=1;
forn(i,Q){
query q = queries[i];
if (!i){
x=q.a; y=q.a;
while (y<=q.b){
addElement(y);
y++;
}
y--;
} else {
while (y<q.b){
y++;
addElement(y);
}
while (y>q.b){
removeElement(y);
y--;
}
while (x<q.a){
removeElement(x);
x++;
}
while (x>q.a){
x--;
addElement(x);
}
}
queries[i].res = elements.size();
}
}
int main(){
cin >> N;
forn(i,N){
cin >> sequence[i+1];
}
cin >> Q;
forn(i,Q){
int buffA, buffB;
cin >> buffA >> buffB;
queries.push_back({buffA,buffB,i,0});
}
M = sqrt(Q);
sort(queries.begin(),queries.end(),moSort);
processQueries();
sort(queries.begin(),queries.end(),byPos);
forn(i,Q){
cout << queries[i].res << endl;
}
return 0;
}
Lo que hice fue usar Mo’s Algorithm para ordenar las Q queries para poder responderlas de forma más eficiente. Tengo dos punteros dentro de mi secuencia de números, uno ‘x’ para el comienzo de mi “ventana” y otro ‘y’ para el final. Esta ventana la represento con un map que usa los números de la secuencia como claves, y la cantidad de apariciones dentro de la ventana como valores.
Al mover ‘y’ hacia la derecha, agrego a mi ventana al elemento sobre el que quedé parado. Si no existía, creo esa clave dentro del map y seteo su valor en 1. Si existía, le sumo 1 al valor de esa clave. Si muevo ‘y’ hacia la izquierda (saco un elemento), le resto 1 al valor de la clave correspondiente al número de la secuencia en donde estaba parado. Si el valor pasa a ser 0, elimino esa clave del map.
Lo mismo para ‘x’, pero al revés. Así, voy agregando o sacando elementos hasta que mis punteros coincidan con la query pedida. El resultado de cada query es el tamaño del map cuando mis punteros ‘x’ e ‘y’ coinciden con el principio y final de la query respectivamente. Cuando terminé de procesarlas todas, las vuelvo a ordenar según su posición original e imprimo el resultado de cada una.
Me gustaría saber cómo puedo agilizar un poco las cosas. No se si es porque hago dos sort, porque estoy ordenando mal las queries, o porque debería usar otra estructura en vez de map (multiset, a lo mejor?).
Saludos!