#include<bits/stdc++.h>
using namespace std;
#define PB push_back
#define F first
#define S second
class FenwickTree
{
private:
int N;
vector<int> arr;
map<int,int> compact;
public:
FenwickTree() {}
FenwickTree(int n,vector<int> v): N(n+5), arr(N,0)
{
for(int i=0;i<v.size();i++)
compact[v[i]]=i;
}
void update(int idx,int val)
{
idx = compact[idx];
idx++;
while(idx<N)
{
arr[idx] += val;
idx += idx & -idx;
}
return ;
}
int query(int idx)
{
idx = compact[idx] - 1;
idx++;
int ret=0;
while(idx>0)
{
ret += arr[idx];
idx -= idx & -idx;
}
return ret;
}
};
int n,q;
int sA[100005],sB[100005];
int qA[100005],qB[100005],qC[100005],ans[100005];
map<int,int> ma,mb;
vector<int> va,vb;
vector<pair<int,pair<int,int> > > poi;
int main()
{
scanf("%d %d",&n,&q);
for(int i=0;i<n;i++)
{
scanf("%d %d",&sA[i],&sB[i]);
poi.PB({ -(sA[i]+sB[i]) , {0,i} });
if(!ma[sA[i]])
{
ma[sA[i]]=1;
va.PB(sA[i]);
}
if(!mb[sB[i]])
{
mb[sB[i]]=1;
vb.PB(sB[i]);
}
}
for(int i=0;i<q;i++)
{
scanf("%d %d %d",&qA[i],&qB[i],&qC[i]);
poi.PB({ -(max(qA[i]+qB[i],qC[i])) , {1,i} });
}
sort(poi.begin(),poi.end());
sort(va.begin(),va.end());
sort(vb.begin(),vb.end());
int all=0;
FenwickTree FwA(va.size(),va),FwB(vb.size(),vb);
for(int i=0;i<poi.size();i++)
{
int ty=poi[i].S.F;
int idx=poi[i].S.S;
if(!ty)
{
all++;
FwA.update(sA[idx],1);
FwB.update(sB[idx],1);
}
else
{
int upA = *(lower_bound(va.begin(),va.end(),qA[idx]));
int upB = *(lower_bound(vb.begin(),vb.end(),qB[idx]));
ans[idx] = all - FwA.query(max(0,upA)) - FwB.query(max(0,upB));
}
}
for(int i=0;i<q;i++)
printf("%d\n",ans[i]);
return 0;
}
Compilation message
examination.cpp: In constructor 'FenwickTree::FenwickTree(int, std::vector<int>)':
examination.cpp:18:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
18 | for(int i=0;i<v.size();i++)
| ~^~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:87:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | for(int i=0;i<poi.size();i++)
| ~^~~~~~~~~~~
examination.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
59 | scanf("%d %d",&n,&q);
| ~~~~~^~~~~~~~~~~~~~~
examination.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
62 | scanf("%d %d",&sA[i],&sB[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
77 | scanf("%d %d %d",&qA[i],&qB[i],&qC[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
394 ms |
21216 KB |
Output is correct |
| 2 |
Incorrect |
376 ms |
21120 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
394 ms |
21216 KB |
Output is correct |
| 2 |
Incorrect |
376 ms |
21120 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
