#include <bits/stdc++.h>
using namespace std;
#define MAXN 200005
int a[MAXN];
int b[MAXN];
int n;
struct node
{
node* nula;
node* kec;
int cnt = 0;
};
node* tree[4*MAXN];
void insert(int nod,int x)
{
if(tree[nod] == NULL)tree[nod]=new node();
node* now = tree[nod];
now->cnt++;
for(int i = 31; i >= 0; i--)
{
if(x&(1<<i))
{
if(now->kec == NULL)now->kec=new node();
now=now->kec;
}
else
{
if(now->nula == NULL)now->nula=new node();
now=now->nula;
}
now->cnt++;
}
}
int querytrie(int nod,int x)
{
//>=x?
if(tree[nod]==NULL)return 0;
node* now = tree[nod];
int ans = 0;
int i;
for(i = 31; i >= 0; i--)
{
if(x&(1<<i))
{
if(now->kec==NULL)break;
now=now->kec;
}
else
{
if(now->kec!=NULL)ans += now->kec->cnt;
if(now->nula==NULL)break;
now=now->nula;
}
}
if(i==-1)ans+=now->cnt;
return ans;
}
void update(int node,int left,int right,int idx,int val)
{
insert(node,val);
if(left==right)
{
return ;
}
int mid = left+right>>1;
if(idx <= mid)update(node*2,left,mid,idx,val);
else update(node*2+1,mid+1,right,idx,val);
}
int query(int node,int left,int right,int l,int r,int val)
{
if(left > right || left > r || l > right)return 0;
if(left >= l && right <= r)return querytrie(node,val);
int mid = left+right>>1;
return query(node*2,left,mid,l,r,val)+query(node*2+1,mid+1,right,l,r,val);
}
struct que
{
int x,y,z;
int id;
};
que qq[MAXN];
bool cmp(que a,que b)
{
return a.x > b.x;
}
bool cmpp(int x,int y)
{
return b[x] < b[y];
}
bool cmppp(int x,int y)
{
return a[x]>a[y];
}
vector <int> ids;
vector <int> idsz;
int pozseg[MAXN];
int findlowb(int x)
{
int lo = 0,hi=n-1,mid=lo+hi>>1,r=n;
while(lo <= hi)
{
if(b[idsz[mid]] >= x)r=mid,hi=mid-1;
else lo=mid+1;
mid = lo+hi>>1;
}
return r;
}
int main()
{
ios_base::sync_with_stdio(false);
int q;
cin >> n >> q;
for(int i = 0; i < n; i++)
{
cin >> a[i] >> b[i];
ids.push_back(i);
}
for(int i = 0; i < q; i++)
{
cin >> qq[i].x >> qq[i].y >> qq[i].z;
qq[i].id=i;
}
sort(qq,qq+q,cmp);
sort(ids.begin(),ids.end(),cmpp);
idsz = ids;
for(int i = 0; i < ids.size(); i++)
{
pozseg[ids[i]]=i;
}
sort(ids.begin(),ids.end(),cmppp);
int now = 0;
for(int i = 0; i < q; i++)
{
while(qq[i].x <= a[ids[now]] && now < n)update(1,0,n-1,pozseg[ids[now]],a[ids[now]]+b[ids[now]]),now++;
cout << query(1,0,n-1,findlowb(qq[i].y),n-1,qq[i].z) << "\n";
}
return 0;
}
/*
5 4
35 100
70 70
45 15
80 40
20 95
20 50 120
10 10 100
60 60 80
0 100 100
*/
Compilation message
examination.cpp: In function 'void update(int, int, int, int, int)':
examination.cpp:68:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
68 | int mid = left+right>>1;
| ~~~~^~~~~~
examination.cpp: In function 'int query(int, int, int, int, int, int)':
examination.cpp:76:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
76 | int mid = left+right>>1;
| ~~~~^~~~~~
examination.cpp: In function 'int findlowb(int)':
examination.cpp:106:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
106 | int lo = 0,hi=n-1,mid=lo+hi>>1,r=n;
| ~~^~~
examination.cpp:111:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
111 | mid = lo+hi>>1;
| ~~^~~
examination.cpp: In function 'int main()':
examination.cpp:134:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
134 | for(int i = 0; i < ids.size(); i++)
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2229 ms |
635556 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2229 ms |
635556 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
