#include <bits/stdc++.h>
using namespace std;
struct node{
long long maths,ict,sum;
int indx;
}a[200005];
bool cmp(node a1,node a2){
return a1.maths < a2.maths;
}
int n,m,pt,seg[800005];
pair <long long,int> d[200005];
long long ct,now,ans[200005];
vector <pair<long long,long long> > u;
vector <pair<pair<long long,long long>,int> > q;
void build (int id,int x,int y){
if (x == y)
seg[id]=0;
else
{
int mid=(x+y)/2;
if (seg[id] != 0){
build(id*2,x,mid);
build(id*2+1,mid+1,y);
}
seg[id]=0;
}
}
void update(int id,int x,int y,int pos){
if (x == y)
seg[id]++;
else
{
int mid=(x+y)/2;
if (pos <= mid) update(id*2,x,mid,pos);
else update(id*2+1,mid+1,y,pos);
seg[id]=seg[id*2]+seg[id*2+1];
}
}
int query(int id,int x,int y,int l,int r){
if (l <= x && y <= r)
return seg[id];
if (l > y || r < x)
return 0;
int mid=(x+y)/2;
return query(id*2,x,mid,l,r)+query(id*2+1,mid+1,y,l,r);
}
void solve(int x,int y){
if (x == y);
else
{
int mid=(x+y)/2;
u.clear(); q.clear();
build(1,1,ct);
for (int i=x;i<=mid;i++){
if (a[i].indx == 0)
u.push_back(make_pair(a[i].ict,a[i].sum));
}
for (int i=mid+1;i<=y;i++){
if (a[i].indx != 0)
q.push_back(make_pair(make_pair(a[i].ict,a[i].sum),a[i].indx));
}
sort(u.begin(),u.end()); sort(q.begin(),q.end());
reverse(u.begin(),u.end()); reverse(q.begin(),q.end());
pt=0;
for (int i=0;i<q.size();i++){
while (pt < (int)u.size() && u[pt].first >= q[i].first.first){
update(1,1,ct,u[pt].second);
pt++;
}
ans[q[i].second]+=query(1,1,ct,q[i].first.second,ct);
}
solve(x,mid);
solve(mid+1,y);
}
}
int main(){
ios::sync_with_stdio(false);
cin >> n >> m;
for (int i=1;i<=n;i++){
cin >> a[i].maths >> a[i].ict;
a[i].sum=a[i].maths+a[i].ict;
d[i]=make_pair(a[i].sum,i);
}
for (int i=n+1;i<=n+m;i++){
cin >> a[i].maths >> a[i].ict >> a[i].sum; a[i].indx=i-n;
d[i]=make_pair(a[i].sum,i);
}
sort(d+1,d+1+n+m); now=1;
for (int i=2;i<=n+m+1;i++){
if (d[i].first != d[i-1].first){
ct++;
for (int j=now;j<i;j++){
a[d[j].second].sum=ct;
}
now=i;
}
}
sort(a+1,a+1+n+m,cmp); reverse(a+1,a+1+n+m);
solve(1,n+m);
for (int i=1;i<=m;i++){
cout << ans[i] << "\n";
}
return 0;
}
Compilation message
examination.cpp: In function 'void solve(int, int)':
examination.cpp:66:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<long long int, long long int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | for (int i=0;i<q.size();i++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
1 ms |
364 KB |
Output is correct |
| 6 |
Correct |
1 ms |
364 KB |
Output is correct |
| 7 |
Correct |
12 ms |
1004 KB |
Output is correct |
| 8 |
Correct |
13 ms |
1004 KB |
Output is correct |
| 9 |
Correct |
12 ms |
1004 KB |
Output is correct |
| 10 |
Correct |
11 ms |
1004 KB |
Output is correct |
| 11 |
Incorrect |
12 ms |
1004 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
483 ms |
17432 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
483 ms |
17432 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
1 ms |
364 KB |
Output is correct |
| 6 |
Correct |
1 ms |
364 KB |
Output is correct |
| 7 |
Correct |
12 ms |
1004 KB |
Output is correct |
| 8 |
Correct |
13 ms |
1004 KB |
Output is correct |
| 9 |
Correct |
12 ms |
1004 KB |
Output is correct |
| 10 |
Correct |
11 ms |
1004 KB |
Output is correct |
| 11 |
Incorrect |
12 ms |
1004 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
