Ciao a tutti, sto provando a risolvere il problema Museo di Pontedera con un Segment Tree, ho appena letto la guida di @MatteoArcari e sono abbastanza sicuro che il problema sia sulla funzione Query perché mi dà corretto il subtask 3 dove la restrizione è che le chiamate di Query vedono solo L=0, R=N-1.
Nel subtask 4 viene chiamata solo la medesima funzione, ma i limiti L, R non sono gli estremi dell’albero. Lascio il codice e lo screenshot della sottoposizione (il Subtask 1 non si vede ma restituisce il giusto valore).
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
struct SegmentTree {
int N;
vector<int> Tree;
int Build(int i, int left, int right, vector<int> &A) {
if (right - left == 1) return Tree[i] = A[left];
int mid = (right + left) / 2;
Tree[i] = max(Build(2*i, left, mid, A), Build(2*i+1, mid, right, A));
return Tree[i];
}
void Start (vector<int> &A) {
N = A.size();
Tree.resize(4 * N);
Build(1, 0, N, A);
}
void Update(int i, int left, int right, int pos, int val) {
if (right - left == 1) {
Tree[i] = val;
return;
}
int mid = (left + right) / 2;
if (pos < mid) Update(2*i, left, mid, pos, val);
else Update(2*i+1, mid, right, pos, val);
Tree[i] = max(Tree[2*i], Tree[2*i+1]);
}
int Query(int i, int left, int right, int query_left, int query_right) {
if (right <= query_left || left >= query_right) return INT_MIN;
if (left >= query_left && right <= query_right) return Tree[i];
int mid = (left + right) /2;
return max(Query(2*i, left, mid, query_left, query_right), Query(2*i+1, mid, right, query_left, query_right));
}
void Update(int pos, int val) {
Update(1, 0, N, pos, val);
}
int Query(int L, int R) {
return Query(1, 0, N, L, R);
}
};
SegmentTree SegTree;
void inizia(int N, vector<int> A) {
SegTree.Start(A);
}
void aggiorna(int P, int X) {
SegTree.Update(P, X);
}
int massimo(int L, int R) {
return SegTree.Query(L, R);
}
