#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX = 1e5;
int bit[MAX + 1];
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, idx, type;
bool operator<(event other){
if(x == other.x) type < other.type;
return x > other.x;
}
};
int n, m;
void solve2(){
vector<event> events;
for(int i = 0; i < n; i++){
int x, y;
cin>>x>>y;
events.push_back({x, y, -1, 0});
}
for(int i = 0; i < m; i++){
int x, y, z;
cin>>x>>y>>z;
events.push_back({x, y, i, 1});
}
sort(events.begin(), events.end());
int ans[m];
for (auto i : events)
{
if(i.type == 0){
update(i.y, 1);
}else{
ans[i.idx] = query(i.y, MAX);
}
}
for (int i = 0; i < m; i++) cout<<ans[i]<<endl;
}
void solve1(){
vector<pair<int, int>> p;
for(int i = 0; i < n; i++){
int x, y;
cin>>x>>y;
p.push_back({x, y});
}
for(int i = 0; i < m; i++){
int x, y, z;
cin>>x>>y>>z;
int cnt = 0;
for(int i = 0; i < n; i++){
if(p[i].first >= x && p[i].second >= y && p[i].first + p[i].second >= z) cnt++;
}
cout<<cnt<<endl;
}
}
int main(){
cin>>n>>m;
if(n <= 3000 && m <= 3000) solve2();
else solve2();
}
Compilation message
examination.cpp: In member function 'bool event::operator<(event)':
examination.cpp:25:31: warning: statement has no effect [-Wunused-value]
25 | if(x == other.x) type < other.type;
| ~~~~~^~~~~~~~~~~~
| # |
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 |
Incorrect |
264 ms |
4912 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
264 ms |
4912 KB |
Output isn't correct |
| 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 |
- |
