#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;
struct BIT{
int n;
vector<int> bt;
void init(int x){
n=x;
bt.resize(x+1);
}
void update(int x,int y){
x++;
for(;x<=n;x+=(x&-x)){
bt[x]+=y;
}
}
int query(int x){
x++;
int ans=0;
for(;x>0;x-=(x&-x)){
ans+=bt[x];
}
return ans;
}
}bt;
vector<int> g;
struct no{
int x,y,z;
int id;
no(int a,int b,int c,int d){
x=a;
y=b;
z=c;
id=d;
}
};
vector<no> v;
vector<int> ans;
void add(int a,int b,int c,int d){
v.push_back({-a,-b,-c,d});
g.push_back(-c);
}
bool cmp(no a,no b){
if(a.x==b.x){
return a.id<b.id;
}
return a.x<b.x;
}
bool cmp2(no a,no b){
if(a.y==b.y){
return a.id<b.id;
}
return a.y<b.y;
}
void dc(int l,int r){
if(l==r){
return;
}
int m=(l+r)/2;
dc(l,m);
dc(m+1,r);
sort(v.begin()+l,v.begin()+m+1,cmp2);
sort(v.begin()+m+1,v.begin()+r+1,cmp2);
int a=l,b=m+1;
while(a<=m || b<=r){
cout << a << " " << b << endl;
if(a>m || (b<=r && !cmp2(v[a],v[b]))){
if(v[b].id<0){
b++;
continue;
}
ans[v[b].id]+=bt.query(v[b].z);
b++;
}
else{
if(v[a].id>=0){
a++;
continue;
}
bt.update(v[a].z,1);
a++;
}
}
for(int i=l;i<=m;i++){
if(v[i].id<0){
bt.update(v[i].z,-1);
}
}
}
int main(){
AquA;
int n,q;
cin >> n >> q;
bt.init(n+q);
for(int i=0;i<n;i++){
int a,b;
cin >> a >> b;
int c=a+b;
add(a,b,c,-1);
}
ans.resize(q);
for(int i=0;i<q;i++){
int a,b,c;
cin >> a >> b >> c;
add(a,b,c,i);
}
sort(g.begin(),g.end());
g.erase(unique(g.begin(),g.end()),g.end());
sort(v.begin(),v.end(),cmp);
for(auto &h:v){
h.z=lower_bound(g.begin(),g.end(),h.z)-g.begin();
cout << h.z << endl;
}
dc(0,n+q-1);
for(int i=0;i<q;i++){
cout << ans[i] << "\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3099 ms |
34676 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3099 ms |
34676 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
