DIVMAC getting wa in SEGMENT TREE

1 
#include <bits/stdc++.h>
using namespace std;
int MAX = 1000000;
long long int tree[4*1000000];
long long int leastprime[1000000+1];
void start(){
    for(int i=0;i<=1000000;i++){
        leastprime[i]=i;
    }
    for(int i=2;i<=sqrt(1000000);i++){
        for(int j=i;j<=1000000;j+=i){
            if(leastprime[j]>i){
                leastprime[j]=i;
            }
        }
    }
    leastprime[0]=1;leastprime[1]=1;
}
int build(int left , int right , int current,int arr[]){
    if(left>right){
        return 0;
    }
    if(left==right){
        tree[current]=leastprime[arr[left]];
        return tree[current];
    }
    int mid=(left+right)/2;
    int a = build(left , mid , (2*current)+1 , arr );
    int b = build(mid+1 , right , (2*current)+2 , arr );
    tree[current] = a>b?a:b;
    return tree[current];
    /*
          2 5 8 10 3 44
          2 5 2 2  3  2
          
          0 => 5  (0,5)
          1 => 5  (0,2)
          2 => 3  (3,5)
          3 => 5  (0,1)
          4 => 2  (2,2)
          5 => 3  (3,4)
          6 => 2  (5,5)
          7 => 2  (0,0)
          8 => 5  (1,1)
          9
          10
          11 => 2  (3,3)
          12 => 3  (4,4)
    */
}
void print(int current){
    for(int i=0;i<current;i++){
        std::cout << tree[i] << " ";
    }
}
int update(int left , int right , int cleft , int cright , int current,int arr[]){
    if(cleft>cright){
        return 0;
    }
    if(cright<left || right<cleft){
        return 0;
    }
    if(tree[current]==1){
        return 0;
    }
    if(cleft==cright){
        if(cleft>=left && cleft<=right){
            arr[cleft] = arr[cleft]/leastprime[arr[cleft]];
            tree[current] = leastprime[arr[cleft]];
            return tree[current];
        }
        else{
            return 0;
        }
    }
    int mid = (cleft+cright)/2;
    int a = update(left,right,cleft,mid,(2*current)+1,arr);
    int b = update(left,right,mid+1,cright,(2*current)+2,arr);
    tree[current] = a>b?a:b;
    return tree[current];
}
int find(int left , int right , int cleft , int cright , int current){
    if(cright<left || right<cleft){
        return 0;
    }
    if(cleft==cright){
        if(cleft>=left && cleft<=right){
            return tree[cleft];
        }
        else{
            return 0;
        }
    }
    if(cleft>=left&&cright<=right){
        return tree[current];
    }
    int mid=(cleft+cright)/2;
    int a = find(left,right,cleft,mid,(2*current)+1);
    int b = find(left,right,mid+1,cright,(2*current)+2);
    return a>b?a:b;
}
int main(){
    start();
    int t;std::cin >> t;
    while(t--){
        int n,m;std::cin >> n>>m;
        int arr[n];
        for(int i=0;i<n;i++){
            std::cin >> arr[i];
        }
        int jk=build(0,n-1,0,arr);
        while(m--){
            int l,r,type;std::cin >> type>>l>>r;
            if(type==0){
                // UPDATE 
                int p =update(l-1,r-1,0,n-1,0,arr);
            }
            else{
                //FIND
                std::cout << find(l-1,r-1,0,n-1,0) <<" ";
                if(m==0){
                    cout<<"\n";
                }
            }
        }
    }
}

plz some one tell me where i am getting mistake , plz

2

current should be initialised with 1

3

I think that the quality of your code could be improved.

See my post on reddit Reddit - Dive into anything

1 Like
4

bro its ur choice . i started with zero so the left and right are 2x+1 , 2x+2 respectively

5

Yes, for this reason I saied that you can improve your solution. If you developed a copy and past segment tree well tested you could be avoid this error.

1 Like
6 
#include <bits/stdc++.h>
using namespace std;
long long int tree[4*1000099];
long long int leastprime[1000099+1];
void start(){
    for(long long int i=0;i<=1000099;i++){
        leastprime[i]=i;
    }
    for(long long int i=2;i<=sqrt(1000099);i++){
        for(long long int j=i;j<=1000099;j+=i){
            if(leastprime[j]>i){
                leastprime[j]=i;
            }
        }
    }
    leastprime[0]=1;leastprime[1]=1;
}
void build(long long int left ,long long int right , long long int current,long long int arr[]){
    if(left>right){
        return ;
    }
    if(left==right){
        tree[current]=leastprime[arr[left]];
        return ;
    }
    long long int mid=(left+right)/2;
    build(left , mid , (2*current)+1 , arr );
    build(mid+1 , right , (2*current)+2 , arr );
    tree[current] = max(tree[(2*current)+2],tree[(2*current)+1]);
    return;
}
void print(long long int current){
    for(long long int i=0;i<current;i++){
        std::cout << tree[i] << " ";
    }
}
void update(long long int left , long long int right , long long int cleft , long long int cright , long long int current,long long int arr[]){
    if(cleft>cright){
        return;
    }
    if(cright<left || right<cleft){
        return;
    }
    if(cleft==cright){
        if(cleft>=left && cleft<=right){
            arr[cleft] = arr[cleft]/leastprime[arr[cleft]];
            tree[current] = leastprime[arr[cleft]];
            return;
        }
        else{
            return;
        }
    }
    if(tree[current]==1){
        return;
    }
    long long int mid = (cleft+cright)/2;
    update(left,right,cleft,mid,(2*current)+1,arr);
    update(left,right,mid+1,cright,(2*current)+2,arr);
    tree[current] = max(tree[(2*current)+2],tree[(2*current)+1]);
    return;
}
long long int find(long long int left ,long long int right ,long long int cleft , long long int cright , long long int current){
    if(tree[current]==1){
        return 1;
    }
    if(cright<left || right<cleft){
        return 1;
    }
    if(cleft==cright){
        if(cleft>=left && cleft<=right){
            return tree[cleft];
        }
        else{
            return 1;
        }
    }
    if(cleft>=left&&cright<=right){
        return tree[current];
    }
    long long int mid=(cleft+cright)/2;
    long long int a = find(left,right,cleft,mid,(2*current)+1);
    long long int b = find(left,right,mid+1,cright,(2*current)+2);
    return max(a,b);
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    start();
    long long int t;std::cin >> t;
    while(t--){
        long long int n,m;std::cin >> n>>m;
        long long int arr[n];
        for(long long int i=0;i<n;i++){
            std::cin >> arr[i];
        }
        build(0,n-1,0,arr);
        while(m--){
            long long int l,r,type;std::cin >> type>>l>>r;
            if(type==0){
                // UPDATE 
                update(l-1,r-1,0,n-1,0,arr);
            }
            else{
                //FIND
                long long int xc=find(l-1,r-1,0,n-1,0);
                std::cout << xc <<" ";
            }
        }
        cout<<"\n";
    }
    return 0;
}

this is the updated but in vain… can anyone find the mistake for wa

9

Mh, I don’t resolve this problem so I can not help you at the moment but I can try this in my free time.

But, for sure I will use my implementation of Segment Tree, and after you can find the error on yours.

If you want try to use a well-tested Segment Tree implementation, you can use this implementation GitHub - vincenzopalazzo/cpstl: Copy and Paste standard library (CPSTL) is a repository with a collection of data structure and algorithms in many different languages

1 Like
10

very nice of u. there is a problem with me. i dont love to use old codes because in this we lose the concept so i write again and again. i am fully confident with my code and also there is a tux other than simply using segment tree in this problem, i dont want to be a spoiler but try , it will also give u headaches :wink: . till then you try . i continue to other problem,

by the way thanks for your link. very helpful

11

I will send an update in the few days :smiley: