Ho provato a scrivere grande muraglia con un segment tree, ma fa solo 10/100. La query del problema è quella di trovare in un array il range entro il quale tutti i numeri sono <= ad un numero ad una certa posizione x(gli estremi sono i primi numeri che sono > al numero). Credo ci sia qualche problema di ottimizzazione, ma non saprei. Ho già provato a calcolare l’estremo destro e quello sinistro in un colpo solo ma non è servito.
#include <bits/stdc++.h>
using namespace std;
vector<int> ST;
int dimensione;
int elementi;
//cout vector
template <typename T>
ostream& operator<<(ostream& o, const vector<T>& v){
o << "[ ";
for(auto i: v){
o << i << " ";
}
o << "]";
return o;
};
pair<int, int> chiedi(int x) {
int rx = dimensione + x;
int h = ST[rx];
stack<pair<int, pair<int, int>>> S;
S.push({1, {0, dimensione}});
pair<int, pair<int, int>> curr;
int a=0;
while (not S.empty()){
curr = S.top();
S.pop();
if(curr.first == rx) continue;
else if(curr.second.second < a) continue;
else if(ST[curr.first] <= h) continue;
else{
if(curr.first < dimensione){
int middle = (curr.second.first + curr.second.second)/2;
if(middle < x){
S.push({curr.first*2 + 1, {middle + 1, curr.second.second}});
S.push({curr.first*2, {curr.second.first, middle}});
}else{
S.push({curr.first*2, {curr.second.first, middle}});
}
}else{
curr.first -= dimensione;
if((a < curr.first) and (curr.first < x)){
a = curr.first;
}
curr.first += dimensione;
}
}
}
S.empty();
S.push({1, {0, dimensione}});
int b=elementi - 1;
while (not S.empty()){
curr = S.top();
S.pop();
if(curr.first == rx) continue;
else if(b < curr.second.first) continue;
else if(ST[curr.first] <= h) continue;
else{
if(curr.first < dimensione){
int middle = (curr.second.first + curr.second.second)/2;
if(middle < x){
S.push({curr.first*2 + 1, {middle + 1, curr.second.second}});
}else{
S.push({curr.first*2, {curr.second.first, middle}});
S.push({curr.first*2 + 1, {middle + 1, curr.second.second}});
}
}else{
curr.first -= dimensione;
if((x < curr.first) and (curr.first < b)){
b = curr.first;
}
curr.first += dimensione;
}
}
}
return {a, min(b, elementi - 1)};
}
void cambia(int x, int h) {
int pos = dimensione + x;
ST[pos] = h;
pos /= 2;
while((pos > 0) and ST[pos] < h){
ST[pos] = h;
pos /= 2;
}
return;
}
void inizializza(int N, vector<int> H) {
dimensione = 1;
elementi = H.size();
while(dimensione < elementi)
dimensione *= 2;
ST = vector<int>(2*dimensione, numeric_limits<int>::min());
int livello = dimensione;
copy(H.begin(), H.end(), ST.begin()+livello);
while(livello > 1){
for(int i=livello+1; i<=(2 * livello); i++){
if(ST[i] > ST[i/2]){
ST[i/2] = ST[i];
}
}
livello /= 2;
}
return;
}
Grazie Mille