#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e5;
struct Data
{
int x, y, p, s;
};
int N, Q;
vector<Data> V;
vector<int> comp;
int ans[MAXN+10];
int getcomp(int x) { return lower_bound(comp.begin(), comp.end(), x)-comp.begin()+1; }
int tree[MAXN+10];
void update(int i, int k) { for(i=N-i+1; i<=N; i+=(i&-i)) tree[i]+=k; }
int query(int i) { int ret=0; for(i=N-i+1; i>0; i-=(i&-i)) ret+=tree[i]; return ret; }
int flush(int i) { for(i=N-i+1; i<=N; i+=(i&-i)) tree[i]=0; }
void solve(int l, int r)
{
if(l==r) return;
int mid=l+r>>1;
solve(l, mid);
solve(mid+1, r);
vector<Data> L, R;
for(int i=l; i<=mid; i++) if(V[i].p==0) L.push_back(V[i]);
for(int i=mid+1; i<=r; i++) if(V[i].p) R.push_back(V[i]);
sort(L.begin(), L.end(), [&](const Data &p, const Data &q) { return p.x>q.x; });
sort(R.begin(), R.end(), [&](const Data &p, const Data &q) { return p.x>q.x; });
for(int i=0, j=0; i<R.size(); i++)
{
for(; j<L.size() && L[j].x>=R[i].x; j++)
{
update(getcomp(L[j].y), 1);
}
ans[R[i].p]+=query(getcomp(R[i].y));
}
for(int j=0; j<L.size(); j++) flush(getcomp(L[j].y));
}
int main()
{
scanf("%d%d", &N, &Q);
for(int i=1; i<=N; i++)
{
int x, y;
scanf("%d%d", &x, &y);
V.push_back({x, y, 0, x+y});
comp.push_back(y);
}
for(int i=1; i<=Q; i++)
{
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
V.push_back({x, y, i, z});
}
sort(comp.begin(), comp.end());
comp.erase(unique(comp.begin(), comp.end()), comp.end());
sort(V.begin(), V.end(), [&](const Data &p, const Data &q)
{
if(p.s!=q.s) return p.s>q.s;
return p.p<q.p;
});
solve(0, V.size()-1);
for(int i=1; i<=Q; i++) printf("%d\n", ans[i]);
}
Compilation message
examination.cpp: In function 'int flush(int)':
examination.cpp:25:61: warning: no return statement in function returning non-void [-Wreturn-type]
25 | int flush(int i) { for(i=N-i+1; i<=N; i+=(i&-i)) tree[i]=0; }
| ^
examination.cpp: In function 'void solve(int, int)':
examination.cpp:30:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
30 | int mid=l+r>>1;
| ~^~
examination.cpp:40:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Data>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | for(int i=0, j=0; i<R.size(); i++)
| ~^~~~~~~~~
examination.cpp:42:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Data>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for(; j<L.size() && L[j].x>=R[i].x; j++)
| ~^~~~~~~~~
examination.cpp:48:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Data>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | for(int j=0; j<L.size(); j++) flush(getcomp(L[j].y));
| ~^~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:53:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
53 | scanf("%d%d", &N, &Q);
| ~~~~~^~~~~~~~~~~~~~~~
examination.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
57 | scanf("%d%d", &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~
examination.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
64 | scanf("%d%d%d", &x, &y, &z);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
102 ms |
11100 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
102 ms |
11100 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
