Can anyone help me with my code?
I don’t what’s wrong with it.
#include<bits/stdc++.h>
using namespace std;
struct Node{
long long int start;//start range
long long int en;//end range
long long int cnt;//to count how many lines in this range are active
Nodeleft;//left sub-segment tree
Noderight;//right sub-segment tree
Node(long long int s,long long int e,long long int x,Nodel,Noder)
{
start=s;
en=e;
cnt=x;
left=l;
right=r;
}
};
struct query{
long long int x1,x2,y1,index,ans;
};
Node* Build(vector&X,long long int s,long long int e)
{
if(s>=e)
return NULL;
if(e-s==1)//we store segment of 1 unit together
return new Node(X[s],X[s+1],0,NULL,NULL);
long long int mid=s+(e-s)/2;
Nodeleft=Build(X,s,mid);
Noderight=Build(X,mid,e);
return new Node(left->start,right->en,0,left,right);
}
void update(Noder,int s,long long int e,long long int val)
{
if(!r||s>=e)
return;
if(s>=r->en||e<=r->start)
return;
if(s<=r->start&&e>=r->en)//range represented by this node completelly totally lies with s and e
r->cnt+=val;
else
{
update(r->left,s,e,val);//update left sub-segment tree
update(r->right,s,e,val);//update right sub-segment tree
if(r->left)
r->cnt=r->left->cnt;
if(r->right)
r->cnt+=r->right->cnt;
}
}
long long int seg_query(Noder,long long int s,long long int e)
{
if(!r||s>=e)
return 0;
if(s>=r->en||e<=r->start)
return 0;
if(s<=r->start&&e>=r->en)
return r->cnt;
else
{
long long int ans1=seg_query(r->left,s,e),ans2=seg_query(r->right,s,e);
return ans1+ans2;
}
}
int main()
{
long long int t;
scanf("%lld\n",&t);
while(t--)
{
long long int n,q;
scanf("%lld%lld",&n,&q);
vector<long long int>x;
vector<struct query>Q;
for(long long int i=1;i<=n;i++)
x.push_back(i);
vector<vector<long long int >>events;
vector<long long int>temp(4,0);
vector<long long int>A;
for(long long int i=0;i<n;i++)
{
long long int a;
cin>>a;
A.push_back(a);
}
for(long long int i=0;i<q;i++)
{
struct query q1;
cin>>q1.x1>>q1.x2>>q1.y1;
q1.index=i;
q1.ans=0;
Q.push_back(q1);
}
sort(Q.begin(),Q.end(),[](struct query&a,struct query&b){
if(a.y1<b.y1)
return true;
return false;
});
//sweep line algorithm is used to solve this problem
for(long long int i=0;i<n-1;i++)
{
long long int x1=i+1,x2=i+2,y1=min(A[i],A[i+1]),y2=max(A[i],A[i+1]);
//start event
temp[0]=x1;
temp[1]=x2;
temp[2]=1;
temp[3]=y1;
events.push_back(temp);
//end event
temp[2]=-1;
temp[3]=y2;
events.push_back(temp);
}
sort(events.begin(),events.end(),[](vector<long long int>&a,vector<long long int>&b){
if((a[3]<b[3])||(a[3]==b[3]&&a[0]<b[0])||(a[3]==b[3]&&a[0]==b[0]&&a[1]<b[1]))
return true;
return false;
});
Node*root=Build(x,0,x.size()-1);
n=events.size();
long long int low=0,high=n-1;
for(long long int i=0;i<q;i++)
{
long long int val=Q[i].y1,index=-1,old_low=low;
high=n-1;
while(low!=-1&&low<=high)
{
long long int mid=low+(high-low)/2;
if(events[mid][3]<=val)
{
index=mid;
low=mid+1;
}
else if(events[mid][3]>val)
{
high=mid-1;
}
}
if(index!=-1)
{
low=index+1;
for(long long int l=old_low;l<=index;l++ )
{
update(root,events[l][0],events[l][1],events[l][2]);
if(events[l][2]==-1&&events[l][3]==val&&events[l][1]<=Q[i].x2&&events[l][1]>Q[i].x1)
Q[i].ans++;
}
}
Q[i].ans+=seg_query(root,Q[i].x1,Q[i].x2);
}
sort(Q.begin(),Q.end(),[](struct query&a,struct query&b){
return a.index<b.index;
});
for(long long int i=0;i<q;i++)
cout<<Q[i].ans<<"\n";
}
}