10/100 Muraglia (TLE)

Aiuto
1

Ciao a tutti, ho iniziato da poco strutture dati e cercando un po’ sono arrivato a quest’implementazione. Mi risolve velocemente solo i task 1 e 2. Non trovo dove sia l’errore, eppure mi sembra che il programma sia N*logN. Qualcuno riesce a darmi qualche consiglio per capire dove sbaglio? Grazie

#include <utility>
#include <vector>
using namespace std;
// variabili globali
vector <int> T;
vector <int> t;
int sizeN;
// "-right" trova l'indice del primo elemento più grande di x a destra
int get_right(int v, int tl, int tr, int l, int r, int x) {
    if(tl > r || tr < l) return -1;
    if(t[v] <= x) return -1;

    if (tl== tr) return tl;

    int tm = tl + (tr-tl)/2;
    int left = get_right(2*v, tl, tm, l, r, x);
    if(left != -1) return left;
    return get_right(2*v+1, tm+1, tr, l ,r, x);
}
// "-left" trova l'indice del primo elemento più grande di x a sinistra
int get_left(int v, int tl, int tr, int l, int r, int x) {
    if(tl > r || tr < l) return -1;
    if(t[v] <= x) return -1;

    if (tl== tr) return tl;

    int tm = tl + (tr-tl)/2;
    int right = get_left(2*v+1, tm+1, tr, l ,r, x);
    if(right != -1) return right;
    return get_left(2*v, tl, tm, l, r, x);
}
//"chiedi" chiama le funzioni "-left" e "-right" e stampa l'output
pair<int, int> chiedi(int x) {
    int right = get_right(1, 0, sizeN-1, x, sizeN-1, T[x]);
    if (right == -1) right = sizeN-1;//se l'elemento non esiste, prendi tutto
    int left = get_left(1, 0, sizeN-1, 0, x, T[x]);
    if (left == -1) left = 0;
    return {left, right};
}
//"update" aggiorna il segment tree in base alla query
void update(int v, int tl, int tr, int pos, int new_val) {
    if (tl == tr) {
        t[v] = new_val;
    } else {
        int tm = (tl + tr) / 2;
        if (pos <= tm)
            update(v*2, tl, tm, pos, new_val);
        else
            update(v*2+1, tm+1, tr, pos, new_val);
        t[v] = max(t[v*2], t[v*2+1]);
    }
}
//"cambia" chiama la funzione "update"
void cambia(int x, int h) {
    T[x] = h;//aggiorna il vettore base
    update(1, 0, sizeN-1, x, h);//aggiorna il segment tree
    return;
}
//"build" costruisce il segment tree
void build(vector <int> a, int v, int tl, int tr) {
    if (tl == tr) {
        t[v] = a[tl];
    } else {
        int tm = (tl + tr) / 2;
        build(a, v*2, tl, tm);
        build(a, v*2+1, tm+1, tr);
        t[v] = max(t[v*2], t[v*2+1]);
    }
}
//"inizializza" prima funzione chiamata: chiama la funzione "build"
void inizializza(int N, vector<int> H) {
    sizeN = N;
    t.resize(4*N);
    T = H;
    build(T, 1, 0, N-1);
	return;
}
2

Alla fine ce l’ho fatta. Ora mi dà 100/100. Secondo voi questo codice viene considerato originale anche se ho preso spunto un po’ dappertutto?

#include <utility> 
#include <vector> 
#include <iostream> 
#include <bits/stdc++.h> 
  
using namespace std;// per leggere da file 
ifstream fin ("input.txt"); 
ofstream fout ("output.txt"); 
// variabili globali 
vector <int> T; 
vector <int> tree; 
int sizeN; 
 
// "-right" trova l'indice del primo elemento più grande di x a destra 
int get_right(int idx, int s, int d, int l, int r, int x) { 
    if(s > r || d < l) return -1; 
 if(l <= s && d <= r) { 
        if(tree[idx] <= x) return -1; 
        while(s != d) { 
            int mid = s + (d-s)/2; 
            if(tree[2*idx] > x) { 
                idx = 2*idx; 
                d = mid; 
            }else { 
                idx = 2*idx+1; 
                s = mid+1; 
            } 
        } 
        return s; 
    } 
 
    int mid = s + (d-s)/2; 
    int left = get_right(2*idx, s, mid, l, r, x); 
    if(left != -1) return left; 
    return get_right(2*idx+1, mid+1, d, l ,r, x); 
} 
 
// "-left" trova l'indice del primo elemento più grande di x a sinistra 
int get_left(int idx, int s, int d, int l, int r, int x) { 
    if(s > r || d < l) return -1; 
  if(l <= s && d <= r) { 
        if(tree[idx] <= x) return -1; 
        while(s != d) { 
            int mid = s + (d-s)/2; 
            if(tree[2*idx+1] > x) { 
                idx = 2*idx+1; 
                s = mid+1; 
            }else { 
                idx = 2*idx; 
                d = mid; 
            } 
        } 
        return s; 
    } 
 
 
    int mid = s + (d-s)/2; 
    int right = get_left(2*idx+1, mid+1, d, l ,r, x); 
    if(right != -1) return right; 
    return get_left(2*idx, s, mid, l, r, x); 
}  
//"chiedi" chiama le funzioni "-left" e "-right" e stampa l'output 
pair<int, int> chiedi(int x) { 
    int right = get_right(1, 0, sizeN-1, x, sizeN-1, T[x]); 
    if (right == -1) right = sizeN-1;//se l'elemento non esiste, prendi tutto 
    int left = get_left(1, 0, sizeN-1, 0, x, T[x]); 
    if (left == -1) left = 0; 
    return {left, right}; 
} 
 
//"update" aggiorna il segment tree in base alla query 
void update(int idx, int s, int d, int pos, int val) { 
    if (s == d) { 
        tree[idx] = val; 
    } else { 
        int mid = (s + d) / 2; 
        if (pos <= mid) 
            update(idx*2, s, mid, pos, val); 
        else 
            update(idx*2+1, mid+1, d, pos, val); 
        tree[idx] = max(tree[idx*2], tree[idx*2+1]); 
    } 
} 
//"cambia" chiama la funzione "update" 
void cambia(int x, int h) { 
    T[x] = h;//aggiorna il vettore base 
    update(1, 0, sizeN-1, x, h);//aggiorna il segment tree 
    return; 
} 
//"build" costruisce il segment tree 
long long int build(int idx,int s, int d){ 
    if(d == s){ 
        return tree[idx]=T[s];} 
  
       int mid= (s+d)/2; 
       tree[idx]= max(build(idx*2,s,mid), build(idx*2+1,mid+1,d)); 
       return tree[idx]; 
  
   } 
//"inizializza" prima funzione chiamata: chiama la funzione "build" 
void inizializza(int N, vector<int> H) { 
    sizeN = N; 
    int realN = 1; 
    while(realN < N) 
    realN *=2; 
    tree.resize(2*realN); 
    T = H; 
    build(1, 0, N-1); 
	return; 
}