#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 2e5;
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 myassert(bool x)
{
if(!x) while(1);
}
void update(int i, int k)
{
myassert(1<=i && i<=N+Q);
for(i=N+Q-i+1; i<=N+Q; i+=(i&-i)) tree[i]+=k;
}
int query(int i)
{
myassert(1<=i && i<=N+Q);
int ret=0;
for(i=N+Q-i+1; i>0; i-=(i&-i)) ret+=tree[i];
return ret;
}
int flush(int i)
{
myassert(1<=i && i<=N+Q);
for(i=N+Q-i+1; i<=N+Q; 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});
comp.push_back(y);
}
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:47:1: warning: no return statement in function returning non-void [-Wreturn-type]
47 | }
| ^
examination.cpp: In function 'void solve(int, int)':
examination.cpp:52:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
52 | int mid=l+r>>1;
| ~^~
examination.cpp:63:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Data>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for(int i=0, j=0; i<R.size(); i++)
| ~^~~~~~~~~
examination.cpp:65:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Data>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | for(; j<L.size() && L[j].x>=R[i].x; j++)
| ~^~~~~~~~~
examination.cpp:71:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Data>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | for(int j=0; j<L.size(); j++) flush(getcomp(L[j].y));
| ~^~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:76:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
76 | scanf("%d%d", &N, &Q);
| ~~~~~^~~~~~~~~~~~~~~~
examination.cpp:80:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
80 | scanf("%d%d", &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~
examination.cpp:87:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
87 | 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 |
107 ms |
10460 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
107 ms |
10460 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 |
- |
