#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX = 1e5;
struct fenwick_tree{
int bit[MAX + 1] = {0};
void update(int pos, int val){
for(int i = pos; i <= MAX; i = i | (i + 1)){
bit[i] += val;
}
}
int query(int pos){
int res = 0;
for(int i = pos; i >= 0; i = (i & (i + 1)) - 1){
res += bit[i];
}
return res;
}
int query(int l, int r){
if(l == 0) return query(r);
return query(r) - query(l - 1);
}
};
struct event{
int x, y, z, idx, type;
bool operator<(event other){
if(z == other.z) return type < other.type;
return z > other.z;
}
};
int n, m;
void solve(){
vector<event> events;
for(int i = 0; i < n; i++){
int x, y;
cin>>x>>y;
events.push_back({x, y, x + y, -1, 0});
}
for(int i = 0; i < m; i++){
int x, y, z;
cin>>x>>y>>z;
events.push_back({x, y, z, i, 1});
}
sort(events.begin(), events.end());
int ans[m];
fenwick_tree X, Y;
int cnt = 0;
for (auto i : events)
{
if(i.type == 0){
Y.update(i.y, 1);
X.update(i.x, 1);
cnt++;
}else{
ans[i.idx] = Y.query(i.y, MAX) + X.query(i.x, MAX) - cnt;
}
}
for (int i = 0; i < m; i++) cout<<ans[i]<<endl;
}
int main(){
cin>>n>>m;
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1000 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
269 ms |
8240 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
269 ms |
8240 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1000 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
