# Grande Muraglia 35/100

**URL:** <https://forum.olinfo.it/t/grande-muraglia-35-100/8882>\
**Category:** Aiuto\
**Created:** [10 Giugno 2024, 10:44pm UTC](https://forum.olinfo.it/t/grande-muraglia-35-100/8882 "2024-06-10T22:44:31Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![Massilla2006](https://forum.olinfo.it/user_avatar/forum.olinfo.it/massilla2006/32/2713_2.png) [@Massilla2006](https://forum.olinfo.it/u/Massilla2006)\
**Post date:** [10 Giugno 2024, 10:44pm UTC](https://forum.olinfo.it/t/grande-muraglia-35-100/8882/1 "2024-06-10T22:44:31Z")

</div>

Ho fatto da poco le ds e sto trovando difficoltà con questo: ho provato un approccio con un segment tree ma va in TLE un po’ ovunque, consigli?

```auto
#include<bits/stdc++.h>
#define ninf INT_MIN
using namespace std;
struct ST{
	
	struct node{
		int val;
		node() : val(ninf){}
		void join(const node &l, const node &r){
			val=max(l.val,r.val);
		}
	};
	
	int real_size;
	vector<node> nodes;
	int size;

	void cst(int n,vector<int> data){
		size=n;
		real_size=1;
		while(real_size<n){
			real_size*=2;
		}
		nodes.assign(2*real_size,node());
		build(1,0,real_size,data);
	}
	
	void build(int u,int l,int r,vector<int> &data){
		if(r-l==1){
			if(l<data.size())
			nodes[u].val=data[l];
		}
		else
		{
			build(2*u,l,(l+r)/2,data);
			build(2*u+1,(l+r)/2,r,data);
			nodes[u].join(nodes[2*u],nodes[2*u+1]);
		}
	}
	
	void update(int pos,int x){
		int u= real_size+pos;
		nodes[u].val=x;
		while(u>1){
			u/=2;
			nodes[u].join(nodes[2*u],nodes[2*u+1]);
		}
	}
	
	int get_max(int u,int l,int r,int x,int y){
		if(x>=r || y<=l) return ninf;
		if(x<=l && y>=r) return nodes[u].val;
		return max(
				get_max(2*u,l,(l+r)/2,x,y),
					get_max(2*u+1,(l+r)/2,r,x,y)
		);
	}
	
	int get_max(int x,int y){
		return get_max(1,0,real_size,x,y);
	}
	
	int spiasx(int l,int r,int h,int x){
		if(get_max(l,r)<=h) return 0;
		if(r-l==1) return l;
		int a=spiasx((r+l)/2,r,h,x);
		if(a!=0) return a;
		int b=spiasx(l,(r+l)/2,h,x);
		if(b!=0) return b;
		return 0;
	}
	int spiadx(int l,int r,int h,int x){
		if(get_max(l,r)<=h){
			if(l==x+1 && r==real_size) return size-1;
			else return 0;
		}
		if(l>=size) return 0;
		if(r-l==1) return l;
		int a=spiadx(l,(r+l)/2,h,x);
		if(a!=0) return a;
		int b=spiadx((r+l)/2,r,h,x);
		if(b!=0) return b;
		return size-1;
	}
	pair<int,int> spia(int x){
		int a,b;
		a=spiasx(0,x,nodes[real_size+x].val,x);
		b=spiadx(x+1,real_size,nodes[real_size+x].val,x);
		return {a,b};
	}
};

ST st;
pair<int, int> chiedi(int x) {
    return st.spia(x);
}

void cambia(int x, int h) {
    st.update(x,h);
}

void inizializza(int N, vector<int> H) {
	st.cst(N,H);
}

```

---

<div class="post-metadata">

**Author:** ![qwfwq](https://forum.olinfo.it/user_avatar/forum.olinfo.it/qwfwq/32/2974_2.png) [@qwfwq](https://forum.olinfo.it/u/qwfwq)\
**Post date:** [12 Giugno 2024, 9:18am UTC](https://forum.olinfo.it/t/grande-muraglia-35-100/8882/2 "2024-06-12T09:18:13Z")

</div>

I tuoi TLE sono determinati dalle funzioni spiasx() e spiadx() che richiamano la funzione get\_max() e ne fanno aumentare la complessità che diventa di tipo quadratica rispetto ad una standard.  
Il tuo codice è sostanzialmente corretto devi solo ridurre la complessità eliminando la funzione get\_max() dalle 2 funzioni spiasx() e spiadx(). Si tratta sostanzialmente di “modificare opportunamente” la prima riga delle 2 funzioni senza usare la funzione get\_max() che non serve poiché ogni nodo ( nodes[u].val ) del segment tree già corrisponde all’altezza max di ogni sotto intervallo.  
Con i dovuti aggiustamenti delle 2 funzioni ottieni alla fine 100.

---

<div class="post-metadata">

**Author:** ![Massilla2006](https://forum.olinfo.it/user_avatar/forum.olinfo.it/massilla2006/32/2713_2.png) [@Massilla2006](https://forum.olinfo.it/u/Massilla2006)\
**Post date:** [12 Giugno 2024, 1:41pm UTC](https://forum.olinfo.it/t/grande-muraglia-35-100/8882/3 "2024-06-12T13:41:48Z")

</div>

Ci avevo pensato ma in effetti l’intervallo di cui richiedo il massimo (l,r) non e’ sempre potenza di 2, quindi non capisco come poter implementare il problema utilizzando i valori massimi che memorizzo nell’albero.

---

<div class="post-metadata">

**Author:** ![qwfwq](https://forum.olinfo.it/user_avatar/forum.olinfo.it/qwfwq/32/2974_2.png) [@qwfwq](https://forum.olinfo.it/u/qwfwq)\
**Post date:** [12 Giugno 2024, 4:49pm UTC](https://forum.olinfo.it/t/grande-muraglia-35-100/8882/4 "2024-06-12T16:49:16Z")

</div>

Dai un’occhiata alla funzione get\_first() che trovi [qui](https://cp-algorithms.com/data_structures/segment_tree.html). È quello che ti serve per le funzioni spiasx() e spiadx() per risolvere il task senza TLE.

---

<div class="post-metadata">

**Author:** ![Massilla2006](https://forum.olinfo.it/user_avatar/forum.olinfo.it/massilla2006/32/2713_2.png) [@Massilla2006](https://forum.olinfo.it/u/Massilla2006)\
**Post date:** [16 Giugno 2024, 1:44am UTC](https://forum.olinfo.it/t/grande-muraglia-35-100/8882/5 "2024-06-16T01:44:58Z")

</div>

Grazie mille, l’ho risolto. Inoltre mi hai linkato un sito davvero interessante quindi grazie ancora 🫶