PRMQ getting wrong answer while 2nd subtask is Getting correct answer

I have applied Segment Tree + Binary search approach.But not getting correct answer for all.Only 2nd task is getting correct answer.

i am storing prime factors in node as pair where first is prime number and second is exponent.

struct node{
    vector<pair<int,int> >pr;
    int size;
};

here is the code.
I have submitted it around 40 times but not able to debug the code.

submitted code

Your program gives a run-time error at input:

1
2
1
1 1 2 2

Correct output is : 1

P.S: Here(CodeChef: Practical coding for everyone ) is a much simpler code using iterative segment trees, my idea is similar to yours. except for every prime number i have added the index ‘i’ which it divides ‘exponent’ number of times. i.e

if 2 divdes (a[i = 1] = 8) 3 times, then (vec[2] = {1,1,1}) and so on.

Your program does give a runtime error. I suspect that instead of giving an error, its going onto undefined behaviour when judge evaluates it.

One of the faulty sections of code i found is-

void sieve(int n=1000001){
		int x = (int)sqrt(n)+1;
		for(int i=2;i<=n;i++){
			if(!fact[i]){
				fact[i]=i;
				if(i<=x){
					for(int j=i*i;j<=n;j+=i){///FAULTY!!

When i >=10^5 , j will be ~10^10 which will cause overflow. fact[j] will then EITHER give undefined behavior OR runtime error, depending on factors. The reason it gave error on divyansh;s compiler while didnt on yours is a sure proof that your program runs on undefined behaviour, and its output will vary from compiler to compiler.

To correct it, declare j as long long int, AND use long long int j=(long long int)i * i . If you dont type cast it, overflow will still occur as i is int, and so i * i will be evaluated as int before being stored.

Correct it and tell me the results ^^

For OP-

The test case giving runtime error is-

Input
10
100003 1 1 1 1 1 1000 4 5 6
1
5 6 1 12
Expected Output
0

Error message -

Program terminated with signal SIGSEGV, Segmentation fault.
#0  0x000000000040190e in QTree::query (this=0x7ffe2eca5e60, l=4, 
    r=<optimized out>, s=<optimized out>, e=4, x=<optimized out>, 
    y=<optimized out>, idx=2) at solution.cc:116
116					return tree[idx].pr[ub].second - (lb<0?0:tree[idx].pr[lb].second);

Thank you @divyansh_gaba7 and @vijju123 for your efforts,
I found the bug which was in my query function

int query(int l,int r,int s, int e,int x,int y, int idx=1){
    if(l>e||r<s)
        return 0;
    if(l<=s&&r>=e){
        int lb = lower_bound(tree[idx].pr.begin(),tree[idx].pr.end(),mp(x,0),cmp)-tree[idx].pr.begin()-1;
        int ub = upper_bound(tree[idx].pr.begin(),tree[idx].pr.end(),mp(y,0),cmp)-tree[idx].pr.begin()-1;
        return tree[idx].pr[ub].second - (lb<0?0:tree[idx].pr[lb].second);
    }
    int mid = (s+e)/2;
    return query(l,r,s,mid,x,y,2*idx) 
            +query(l,r,mid+1,e,x,y,2*idx+1);
}

In case of negative ub it was picking garbage value.

return (ub<0?0:tree[idx].pr[ub].second) - (lb<0?0:tree[idx].pr[lb].second);

No…it does not give run-time error. It is giving 1.
And my solution gives WA on submission. you can see

1 Like

That is very weird. It doesn’t give any output on my compiler. Looking into it.

j = i+i; should work as well. UPD :tried changing that still wrong answer.

We’re updating j as j+=i , so i dont think j=i+1 will be compatible with this. Either we do j++ with j=i+1, or use j=i x i, j+=i.

BTW, yes, there must be some other error. I am still getting runtime error on that test case.

i wrote i +i , as in j = 2*i , CodeChef: Practical coding for everyone
Thats what i used here, works fine

Ya, that will work fine. j=2 x i is what most people use. I was saying j=i+1 and j+=i will probably mess things up.

i am using it on ideone

Recheck your query function.

1 Like

886554 14955 4636 26447 29393 3882 7404 11506 27635 20713 11912 22740 5734 221 - Pastebin.com Another test case that gives run-time error. Only entering the values of a[n] gives error. shows there is some bug in construct() as well.
P.S : correct output for above test 0000004100004010004000000020 - Pastebin.com

It can be that the error in construct is also causing the error in query. Sometimes it can be really tricky to debug, esp. when error at one place affects some other part of code (instead of the part where error is)

value of x is 1001 in sieve function…which maximum value of j is ~10^6

2 ≤ a[i] ≤ 10^6 , where 1 ≤ i ≤ N

take a look at this Pasteboard - Uploaded Image

i have made a little changes but still not accepted.
and not getting any runtime error on gcc version 4.8.4 (Ubuntu 4.8.4-2ubuntu1~14.04.3) .

Ok i saw that if statement just now. Then whats the point of running i till n??

@vijju123 so primes greater than sqrt(n) can be marked. example 1003

yeah…that is for marking.