Ciao a tutti, stavo provando a risolvere questo problema " Training - Implement a segment tree (olinfo.it) ", puntando a fare 60 punti (non ho implementato get_min e lower_bound, li farò in un altro momento), ma comunque, ottengo 0/100 con questo codice, nonostante l’esempio (da cui ho tolto le chiamate get_min e lower_bound) funzioni:
Questo è l'input dell'esempio senza get_min e lower bound
10 16
17 -15 13 27 -29 -6 -15 -29 1 -9
1 2 10
2 0 9 4
3 2 4 -22
3 6 7 3
1 0 6
3 1 9 1
3 5 10 22
3 9 10 0
1 7 10
2 0 7 -5
3 1 5 15
2 0 9 -15
1 1 10
1 7 10
1 7 8
1 0 10
output: -47 -61 44 18 14 7 19 (che è corretto, allego anche uno screen dell’output).
Comunque, essendo una delle prime volte in cui implemento un segment tree, ho seguito quasi alla lettera questa guida Efficient and easy segment trees - Codeforces che spiega i segment tree iterativi (mi hanno detto che sono più efficienti e semplici da capire);
Nonostante questo, mi dà 0/100 e dopo svariate ore passate a provare a debuggarlo, nn riesco ancora a capire quale sia il problema…
Codice
#include <iostream>
#include <vector>
using namespace std;
#define _showTree cout<<"Segment Tree: "<<endl;for (auto it: SegTree)cout<<it.first<<" ";cout<<endl;
#define _showLazy cout<<"Lazy propagation: "<<endl;for(auto it: Lazyprop)cout<<it<<" "; cout<<endl;
int len, h;
vector<pair<long long, long long>> SegTree;
vector<long long> Lazyprop;
void init(vector<long long> a){
len = a.size();
SegTree.resize(2 * len);
Lazyprop.resize(len+1, 0);
for(int i = 0; i < len; i++){
SegTree[i+len].first = a[i];
//SegTree[i+len].second = a[i];
}
//store sums in the first segment tree
for(int i = len-1; i > 0; i--)
SegTree[i].first = SegTree[i << 1].first + SegTree[i << 1 | 1].first;
//keep minimum in the 2^ segment tree
//for(int i = len-1; i > 0; i--)
//SegTree[i].second=min(SegTree[i*2].second, SegTree[i*2 + 1].second);
//_showTree
}
//add value to the element in interval [l, r) --> l include, r not included.
void update(int pos, int value, int k) {
SegTree[pos].first += (value * k);
//if the node is a parent, we won't update the children but take note of the increment in order to do it later:
if(pos < len)
Lazyprop[pos] += value;
}
void calculateValue (int pos, int k){
SegTree[pos].first = SegTree[pos << 1].first + SegTree[pos << 1 | 1].first + Lazyprop[pos] * k;
}
void updateParents(int l, int r){
//_showTree
int k = 2;
l += len, r += len - 1;
for(; l > 1; k <<= 1){
l >>= 1, r >>= 1;
for(int i = r; i >= l; i--){
calculateValue(i, k);
}
}
}
void push(int l, int r) { //propagate to children only if needed (Lazyprop[pos] != 0)
int he = h, k = 1 << (h-1);
for(l += len, r += len - 1; he > 0; he--, k >>= 1){
for(int i = (l >> he); i <= r >> he; i++){
if(Lazyprop[i] != 0){
update((i << 1), Lazyprop[i], k);
update((i << 1 | 1), Lazyprop[i], k);
Lazyprop[i] = 0;
}
}
}
}
long long get_sum(int l, int r){ // the interval is [l, r) --> l included and r not included.
long long sum=0;
push(l, l + 1); push(r - 1, r); //propagates to children
l +=len; r += len;
//_showTree
for(; l < r; l >>= 1, r >>= 1){
/*if l (the node considered) is odd, it means you're processing the right child, so it must be taken.
however, you can take their sum from their parent (l/=2 and r/=2)*/
if(l&1) {
sum += SegTree[l++].first;
}
//only if r is odd (if you're processing both left and right childrens)
if(r&1) {
sum += SegTree[--r].first;
}
}
//cout<<endl;
//_showTree _showLazy
return sum;
}
void add(int l, int r, long long value){
if(value == 0) return;
int lstart = l, rstart = r, k = 1;
l += len; r += len;
for(; l < r; l >>= 1, r >>= 1, k <<= 1){
if(l&1)
update(l++, value, k);
if(r&1)
update(--r, value, k);
}
//_showTree cout<<endl; _showLazy
//propagate only to the parents (propagating to parents is necessary, but it's not the same for children)
updateParents(lstart, lstart + 1); updateParents(rstart - 1, rstart);
//_showTree cout<<endl; _showLazy
}
void set_range(int l, int r, long long x)
{
int lstart = l, rstart = r;
push(l, l + 1); push(r - 1, r);
l += len; r += len;
for (int i = l; i < r; i++) {
Lazyprop[i] = 0;
SegTree[i].first = x;
for (int j = i >> 1; j > 0; j >>= 1) {
SegTree[j].first = SegTree[j * 2].first + SegTree[j * 2 + 1].first;
}
}
}
long long get_min(int l, int r){
return 0;
}
int lower_bound(int l, int r, long long x){
return 0;
};
/*int main(int argc, char *argv[]) {
int n, q;
cin >> n >> q;
h = sizeof(int) * 8 - __builtin_clz(n);
vector<long long>a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
init(a);
for (int i = 0; i < q; i++) {
int op, l, r;
long long x;
cin >> op;
cin >> l >> r;
if (op == 2 or op == 3 or op == 5)
cin >> x;
if (op == 1) cout <<get_sum(l, r) << "\n";
if (op == 2) add(l, r, x);
if (op == 3) set_range(l, r, x);
//if (op == 4) cout <<"min "<< get_min(l, r) << "\n";
//if (op == 5) cout << lower_bound(l, r, x) << "\n";
cout<<endl;
}
return 0; }*/
Probabilmente, l’execution killed error si verifica all’interno del set_range pk in una soluzione precedente ottengo 20/100 e l’unica modifica è stata nel set_range (con queste modifiche il set_range fa 20/100, però sbaglia l’esempio, quindi è probabile che sia sbagliato):
set_range() che fa 20/100
void set_range(int l, int r, long long x)
{
int lstart = l, rstart = r;
l += len; r += len;
push(l - len, l - len + 1);
for (int i = l; i < r; i++) {
SegTree[i].first = x;
Lazyprop[i - len] = 0;
for (int j = i >> 1; j > 0; j >>= 1) {
SegTree[j].first = SegTree[j * 2].first + SegTree[j * 2 + 1].first;
}
}
}
Ringrazio in anticipo chi mi risponde e se avete dubbi sul codice che ho scritto fatemelo sapere.
Allego di sotto gli screen dei risultati degli output se vi possono essere utili.
