#include "bits/stdc++.h"
using namespace std;
#ifdef N_N_C
#include "debug.h"
#else
#define cebug(...) "Arya"
#endif
#define ll long long
const int N=5e5+5;
const int mod=1e9+7;
struct Point{
int x,y,z,id,v;
bool operator < (const Point &o){
if(x==o.x){
if(y==o.y) return z>o.z;
return y>o.y;
}
return x<o.x;
}
};
vector <Point> v,v1;
int n,q,ans[N],ans1[N];
vector <int> compress;
int f(int x){
return lower_bound(compress.begin(),compress.end(),x)-compress.begin()+1;
}
struct BIT{
#define gb(x) (x&(-x))
int n;
vector <int> bit;
void init(int _n){
bit.resize(_n,0);
n=_n;
}
void update(int pos, int val){
int i=pos;
for (; i<n; i+=gb(i)) bit[i]+=val;
}
int get(int pos){
int ans=0,i=pos;
for (; i; i-=gb(i)) ans+=bit[i];
return ans;
}
}fw;
void cdq(int l, int r){
if(l+1==r) return;
int mid=(l+r)>>1;
cdq(l,mid);
cdq(mid,r);
vector <Point> tmp;
vector <int> record;
int a=l,b=mid;
while(a<mid and b<r){
if(v[a].y<=v[b].y) fw.update(v[a].z,v[a].v),record.push_back(a),tmp.push_back(v[a++]);
else ans[v[b].id]+=fw.get(v[b].z),tmp.push_back(v[b++]);
}
while(a<mid) tmp.push_back(v[a++]);
while(b<r) ans[v[b].id]+=fw.get(v[b].z),tmp.push_back(v[b++]);
for(auto a:record) fw.update(v[a].z,-v[a].v);
for(int i=l; i<r; i++) v[i]=tmp[i-l];
vector <int> ().swap(record);
vector <Point> ().swap(tmp);
}
void sol(){
// count pair i j : i_x<j_x, i_x<j_y, i_z<j_z
fw.init(N);
cin>>n>>q;
for(int i=1; i<=n; i++){
int x,y;
cin>>x>>y;
v.push_back({-x,-y,-x-y,i,1});
compress.push_back(-x);
compress.push_back(-y);
compress.push_back(-x-y);
}
for(int i=1; i<=q; i++){
int x,y,z;
cin>>x>>y>>z;
v.push_back({-x,-y,-z,n+i,0});
compress.push_back(-x);
compress.push_back(-y);
compress.push_back(-z);
}
sort(compress.begin(),compress.end());
compress.erase(unique(compress.begin(),compress.end()),compress.end());
for(auto &[x,y,z,i,v]:v){
x=f(x);
y=f(y);
z=f(z);
}
sort(v.begin(),v.end());
cdq(0,(int)v.size());
for(int i=n+1; i<=n+q; i++) cout<<ans[i]<<"\n";
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// freopen(".inp", "r", stdin);
// freopen(".out", "w", stdout);
int tt=1;
//cin>>tt;
while(tt--){
sol();
}
cerr << "\nTime elapsed: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
return 0;
}
/** /\_/\
* (= ._.)
* / >💖 \>💕
**/
Compilation message
examination.cpp:112:9: warning: "/*" within comment [-Wcomment]
112 | /** /\_/\
|
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4456 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 7 |
Correct |
8 ms |
4776 KB |
Output is correct |
| 8 |
Correct |
10 ms |
4952 KB |
Output is correct |
| 9 |
Correct |
8 ms |
4956 KB |
Output is correct |
| 10 |
Correct |
8 ms |
4800 KB |
Output is correct |
| 11 |
Incorrect |
6 ms |
4956 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
287 ms |
22128 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
287 ms |
22128 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4456 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 7 |
Correct |
8 ms |
4776 KB |
Output is correct |
| 8 |
Correct |
10 ms |
4952 KB |
Output is correct |
| 9 |
Correct |
8 ms |
4956 KB |
Output is correct |
| 10 |
Correct |
8 ms |
4800 KB |
Output is correct |
| 11 |
Incorrect |
6 ms |
4956 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
