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.
Your program gives a run-time error at input:
1
2
1
1 1 2 2
Correct output is : 1
P.S: Here(https://www.codechef.com/viewsolution/14060497 ) 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.
No…it does not give run-time error. It is giving 1.
And my solution gives WA on submission. you can see
That is very weird. It doesn’t give any output on my compiler. Looking into it.
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);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 , https://www.codechef.com/viewsolution/14060497
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.
https://pastebin.com/4T8brXjB 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 https://pastebin.com/zNEdtE3d
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
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??
yeah…that is for marking.
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);