#include <bits/stdc++.h>
#define ll long long
using namespace std;
map<ll,ll> mp;
struct edge{
ll a,b,c,id,ope;
}op[500005];
ll n,q,ct,ans[500005],x,y,z;
vector<ll> v;
void discretize()
{
sort(v.begin(),v.end());
for (int i=0;i<v.size();i++){
if (!mp[v[i]]) mp[v[i]]=++ct;
}
for (int i=1;i<=n+q;i++){
op[i].a=mp[op[i].a];
op[i].b=mp[op[i].b];
op[i].c=mp[op[i].c];
}
}
int cmp(edge l,edge r)
{
if (l.a!=r.a) return l.a>r.a;
else if (l.b!=r.b) return l.b<r.b;
else if (l.c<r.c) return l.c<r.c;
else return l.id<r.id;
}
int cmp1(edge l,edge r)
{
if (l.c!=r.c) return l.c>r.c;
else if (l.b!=r.b) return l.b<r.b;
else return l.id<r.id;
}
ll t[1000005<<2];
void update(int id,int x,int y,int p,int v)
{
if (x==y){
t[id]+=v;
return;
}
int mid=(x+y)/2;
if (p<=mid) update(id*2,x,mid,p,v);
else update(id*2+1,mid+1,y,p,v);
t[id]=t[id*2]+t[id*2+1];
}
ll query(int id,int x,int y,int l,int r)
{
if (l<=x&&y<=r) return t[id];
if (x>r||y<l) return 0;
int mid=(x+y)/2;
return query(id*2,x,mid,l,r)+query(id*2+1,mid+1,y,l,r);
}
void cdq(int l,int r)
{
if (l>=r) return;
int mid=(l+r)/2;
cdq(l,mid);cdq(mid+1,r);
sort(op+l,op+r+1,cmp1);
for (int i=l;i<=r;i++){
if (op[i].id<=mid&&!op[i].ope) update(1,1,ct,op[i].b,1);
if (op[i].id>mid&&op[i].ope) {
ans[op[i].id-n]+=query(1,1,ct,1,op[i].b);
//cout<<op[i].id-n<<" "<<query(1,1,ct,1,op[i].b)<<"\n";
}
}
for (int i=l;i<=r;i++){
if (op[i].id<=mid&&!op[i].ope) update(1,1,ct,op[i].b,-1);
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>q;
for (int i=1;i<=n;i++){
cin>>op[i].a>>op[i].b;
op[i].c=op[i].a+op[i].b;
op[i].id=i;
v.push_back(op[i].a);
v.push_back(op[i].b);
v.push_back(op[i].c);
}
for (int i=n+1;i<=n+q;i++){
cin>>op[i].a>>op[i].b>>op[i].c;
op[i].id=i,op[i].ope=1;
v.push_back(op[i].a);
v.push_back(op[i].b);
v.push_back(op[i].c);
}
discretize();
sort(op+1,op+1+n+q,cmp);
for (int i=1;i<=n+q;i++) {
cout<<op[i].ope<<" "<<op[i].id<<" "<<op[i].a<<" "<<op[i].b<<" "<<op[i].c<<"\n";
}
cdq(1,n+q);
for (int i=1;i<=q;i++) cout<<ans[i]<<"\n";
}
Compilation message
examination.cpp: In function 'void discretize()':
examination.cpp:13:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
13 | for (int i=0;i<v.size();i++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1901 ms |
33096 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1901 ms |
33096 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
