Ciao a tutti, ho bisogno di aiuto per risolvere il problema Museo di Pontedera.
Ho visto la guida sui segment tree allegata al capitolo e ho provato ad usarli per risolvere il problema. Credo di aver fatto casino da qualche parte, perché quello che mi aspettavo era che il grader mi insultasse in 45 lingue diverse per degli errori nel codice (cosa che probabilmente avrei sistemato senza particolari problemi), invece il processo di compilazione avviene bello liscio e le risposte che produco sono pure corrette, ma il programma è tanto efficiente quanto il mio tentativo precedente (il loop molto molto basic, con time complexity O(n*n)). Non ho la più pallida idea del perché, però…
Ecco il mio codice:
#include <vector>
using namespace std;
struct SegTree {
int N{};
vector<int> st;
int build(int i, int left, int right, vector<int>& A) {
if (right - left == 1) {
return st[i] = A[left];
}
int mid = (left + right) / 2;
st[i] = (build(2 * i, left, mid, A) > build(2 * i + 1, mid, right, A) ?
build(2 * i, left, mid, A) : build(2 * i + 1, mid, right, A));
return st[i];
}
void inizia(vector<int> &A)
{
N = A.size();
st.resize(4 * N);
SegTree::build(1, 0, N, A);
}
void update(int i, int left, int right, int pos, int val) {
if (right - left == 1) {
st[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);
}
st[i] = max(st[2 * i], st[2 * i + 1]);
}
void update(int pos, int val) {
update(1, 0, N, pos, val);
}
int query(int i, int left, int right, int query_left, int query_right) {
if (query_left >= right || query_right <= left) {
return 0;
}
if (left >= query_left && right <= query_right) {
return st[i];
}
int mid = (left + right) / 2;
return (query(2 * i, left, mid, query_left, query_right) >
query(2 * i + 1, mid, right, query_left, query_right) ?
query(2 * i, left, mid, query_left, query_right) :
query(2 * i + 1, mid, right, query_left, query_right));
}
int query(int query_left, int query_right) {
return query(1, 0, N, query_left, query_right+1);
}
};
SegTree segtree{};
void inizia(int N, vector<int> A)
{
segtree.SegTree::inizia(A);
}
void aggiorna(int P, int X)
{
segtree.SegTree::update(P, X);
}
int massimo(int L, int R)
{
return segtree.SegTree::query(L, R);
}
Ho scritto per aiuto su un altro capitolo abbastanza di recente (aka ieri) e mi scuso per questo, ma mi mancano solo 25 punti alla qualificazione per le finali nazionali delle oii e mi sto mangiando la scrivania per vendetta contro gli alberi siccome è da tutta la mattina che provo a risolvere questo problema.
Prometto che dopo questo post sto zitto!
Scusate ancora per il disturbo e grazie mille in anticipo!