Here is the Python Solution
plagiarism ////////////////
433 thats a big hit!
definitely worth it .
Your approach is correct but you have made an implementation mistake if the query is towards the end.
Eg for case
1
5 1
aaaaa
3 5
Your code gives NO but answer is YES.
yes i realised my mistake, i used upperbound on L rather than L-1, i corrected it. thanks for the reply anyway
This is precizely the reason i mentioned segment tree instead of prefix sums, but seeing the comments, i should have mentioned that one too.
I think there’s error indexing. You made segtree indices 0-based, but didnt adjust queries.
Try decrementing both l and r by 1.
That’s all i could find now
We use segtree to find the OR of a range. At each internal node, we take the OR of children. For each query, we split query segment into logN parts, and return OR of all parts. This is a standard application of segment tree.
I got my mistake, got AC…
I too used the same approach but got WA
can someone please look into my code and tell me why i am getting runtime error.
#include <bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t–){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
long long int n,q,i,j,l,r;
cin>>n>>q;
long long int v[n]={0},b[n]={0};
string str;
cin>>str;
if(n<3){
while(q–){
cin>>l>>r;
cout<<“NO”<<endl;
}
continue;
}
for(i=0;i<n-2;i++){
j=i+1;
if(str[j]==str[i]||str[j+1]==str[i]||str[j]==str[j+1]){
v[i]=1;
}
else
v[i]=0;
if(i>0)
b[i]=b[i-1]+v[i];
else
b[i]=v[i];
}
while(q–){
cin>>l>>r;
l–;
r–;
if((r-l+1)<3){
cout<<“NO”<<endl;
continue;
}
if((l-1)>=0 && (b[r-2]-b[l-1])>0){
cout<<“YES”<<endl;
}
else if(l==0 && ((b[r-2]-b[l])>0 || b [0]==1)){
cout<<“YES”<<endl;
}
else
cout<<“NO”<<endl;
}
}
return 0;
}
No,its AC. Just take care about the l and l+1 elements carefully , you will get it try on copy
I still don’t understand how are range min queries or segment trees of any use here? The Setter’s solution make sense. Can you give some idea how can we solve the problem using segment trees?