Muraglia: Exection Timed Out 4s

Sto cercando di risolvere muraglia, ma mi esce execution timed out per la maggior parte dei subtask, il problema è che superano tutti i 4 secondi, io pensavo che a 1 secondo si fermasse direttamente, quindi non capisco se c’è qualche errore strano nel mio programma. Qualcuno potrebbe aiutarmi a controllarlo e magari anche a migliorarlo grazie.
Sto cercando di risolverlo con un segment tree. Questo è il programma:

#include <bits/stdc++.h>
#include <utility>
#include <iostream>
#include <vector>
#define ls (o<<1)
#define rs (o<<1|1)
#define mid (l+r>>1)
using namespace std;
const int T = 10e6;
long long tree[4*T], c=0, A;
vector<long long> B;

void build(int o,int l,int r, vector<int> H);
void cambia(int x, int h);
int get(int o, int l, int r, int x, int a_x);
pair<int, int> chiedi(int x);
int get1(int o, int l, int r, int x, int a_x);
void cambia1(int o,int l,int r,int x,int h);
int get3(int o, int l, int r, int x);

pair<int, int> chiedi(int x){
	pair<int,int> ans;
	if(x<1){
		ans.second=get3(1,0,A-1,B[x]);
		ans.first=0;	
	}
	else{
		ans.first=get1(1,0,A-1,x,B[x]);
		ans.second=get(1,0,A-1,x,B[x]);
	}
	if(ans.second==0)
		ans.second=A-1;
	return ans;
}
void cambia(int x, int h){
	B[x]=h;
	cambia1(1,0,A-1,x,h);
}
void inizializza(int N, vector<int> H){
	build(1,0,N-1,H);
	A=N;
	for(int i=0;i<N;i++){
		B.push_back(H[i]);
	}
}
void cambia1(int o,int l,int r,int x,int h){
	/*if(r<x||l>x) return;          
    if(l==r&&l==x)               
    {
        tree[o]=h;                  
        return;
    }
    cambia1(ls,l,mid,x,h);         
    cambia1(rs,mid+1,r,x,h);     
    tree[o] = max(tree[ls],tree[rs]);*/
	if(l==r) {
        tree[o]=h;return ;
    }
    if(x<=mid) cambia1(ls,l,mid,x,h);
    else cambia1(rs,mid+1,r,x,h);
    tree[o] = max(tree[ls],tree[rs]);  
}
void build(int o,int l,int r, vector<int> H){
    if(l==r){
  		tree[o]=H[c];
  		c++;
		return;
 	}
    build(ls,l,mid,H);
    build(rs,mid+1,r,H);
    tree[o] = max(tree[ls],tree[rs]);
}
int get3(int o, int l, int r, int x) {
    if (l == r) return l;
    return tree[ls] > x ? get3(ls, l, mid, x) : get3(rs, mid+1, r, x);
}
int get(int o, int l, int r, int x, int a_x){
	if(tree[o]<=a_x)
		return 0;
	if(r<=x) 
		return 0;
	if(l==r) 
		return l;
	int ans=get(ls,l,mid,x,a_x);
	return ans
		?ans
		:get(rs,mid+1,r,x,a_x);
}
int get1(int o, int l, int r, int x, int a_x){
	if(tree[o]<=a_x)
		return 0;
	if(l>=x) 
		return 0;
	if(l==r) 
		return l;
	int ans=get1(rs,mid+1,r,x,a_x);
	return ans
		?ans
		:get1(ls,l,mid,x,a_x);
}

Un’altra domanda, ho visto che alcune persone usa no bbst o stack, se il mio programma non può essere migliorato potreste darmi uno spunto su come usare bbst o stack?

Ciao, io sono riuscito a risolvere il problema tramite un Segment Tree e penso che sia più che sufficiente per non andare in TLE. In quanto i segment tree sono strutture dati un po’ complicate, penso che la migliore risorsa che ti possa fornire è il link a questo sito che illustra dettagliatamente l’implementazione in C++ della struttura.

Spero di essere stato d’aiuto!