#include "bits/stdc++.h"
using namespace std;
#ifdef N_N_C
#include "debug.h"
#else
#define cebug(...) "Arya"
#endif
#define int long long
const int N=1e5+5;
const int mod=1e9+7;
struct Point{
int x,y,z,id;
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];
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; i-=gb(i)) bit[i]+=val;
}
int get(int pos){
int ans=0,i=pos;
for (; i<n; 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,1),record.push_back(v[a].z),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(int i=l; i<r; i++) v[i]=tmp[i-l];
for(auto x:record) fw.update(x,-1);
vector <int> ().swap(record);
vector <Point> ().swap(tmp);
}
void cdq1(int l, int r){
if(l+1==r) return;
int mid=(l+r)>>1;
cdq1(l,mid);
cdq1(mid,r);
vector <Point> tmp;
vector <int> record;
int a=l,b=mid;
while(a<mid and b<r){
if(v1[a].y>=v1[b].y) fw.update(v1[a].z,1),record.push_back(v1[a].z),tmp.push_back(v1[a++]);
else ans1[v1[b].id]+=fw.get(v1[b].z),tmp.push_back(v1[b++]);
}
while(a<mid) tmp.push_back(v1[a++]);
while(b<r) ans1[v1[b].id]+=fw.get(v1[b].z),tmp.push_back(v1[b++]);
for(int i=l; i<r; i++) v1[i]=tmp[i-l];
for(auto x:record) fw.update(x,-1);
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});
}
for(int i=1; i<=q; i++){
int x,y,z;
cin>>x>>y>>z;
v.push_back({x,y,z,n+i});
v1.push_back({x,y,z,n+i});
}
sort(v.begin(),v.end());
cdq(0,(int)v.size());
sort(v1.begin(),v1.end());
cdq1(0,(int)v1.size());
for(int i=n+1; i<=n+q; i++) cout<<ans[i]-ans1[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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1112 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1112 KB |
Output is correct |
| 3 |
Correct |
0 ms |
1116 KB |
Output is correct |
| 4 |
Runtime error |
1 ms |
2140 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3061 ms |
14828 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3061 ms |
14828 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1112 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1112 KB |
Output is correct |
| 3 |
Correct |
0 ms |
1116 KB |
Output is correct |
| 4 |
Runtime error |
1 ms |
2140 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
