Count Catchable Fish
Autumn Tournament (2024)
Submission name: fishes.cpp
Problem summary
A fisherman at (a,0) with rod length l can catch a fish (x,y) exactly when y+|a−x|≤l. Count the catchable fish separately for every fisherman; a fish may be counted for several fishermen.
Input
m; m x-coordinates; m y-coordinates; n; n fisherman coordinates; n rod lengths.
Output
n counts in original fisherman order.
Constraints
1≤n,m≤200000; all coordinates and lengths are positive integers at most10^9.
Worked example
Original statement sample.
Input
8 8 10 5 1 2 8 3 1 8 1 4 5 1 6 1 4 3 1 2 6 2 6 7
Output
1 4 4
Solution analysis
- Rewrite the distance condition as two inequalities: x+y≤a+l and y−x≤l−a. A fish is now a point (u,v); a fisherman asks how many points lie in the lower-left rectangle ending at (a+l,l−a). This converts the geometric diamond into a two-dimensional prefix count.
- Sort fish by u and fisherman queries by their first bound. Before answering a query, insert every fish with u≤its bound. A Fenwick tree over compressed v-coordinates counts inserted fish with v≤the second bound. Save answers by original query index.
- In the sample, the fisherman at a=1,l=2 has bounds(3,1), admitting only fish(2,1). Fishermen at2 and6 each admit four fish. Equality is allowed, so insertion and prefix queries must include boundary points.
Why it works
The transformed inequalities are equivalent to the original absolute-value inequality. At query time the sweep has inserted exactly fish satisfying the first inequality, and the Fenwick prefix includes exactly those also satisfying the second. Thus each and only each catchable fish is counted.
Watch out. Use upper_bound for inclusive thresholds, not lower_bound. Negative transformed v values are valid. Do not remove a fish after counting it: fishermen are independent.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<utility>
#include<vector>
using namespace std;
struct Query{
long long u;
long long v;
int index;
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int m;
cin>>m;
vector<long long>x(m),y(m);
for(long long&value:x){
cin>>value;
}
for(long long&value:y){
cin>>value;
}
vector<pair<long long,long long>>fish(m);
vector<long long>coordinates;
for(int i=0;i<m;i++){
fish[i]={x[i]+y[i],y[i]-x[i]};
coordinates.push_back(fish[i].second);
}
int n;
cin>>n;
vector<long long>a(n),length(n);
for(long long&value:a){
cin>>value;
}
for(long long&value:length){
cin>>value;
}
vector<Query>queries(n);
for(int i=0;i<n;i++){
queries[i]={a[i]+length[i],length[i]-a[i],i};
}
sort(fish.begin(),fish.end());
sort(coordinates.begin(),coordinates.end());
coordinates.erase(unique(coordinates.begin(),coordinates.end()),coordinates.end());
sort(queries.begin(),queries.end(),[](const Query&a,const Query&b){
return a.u<b.u;
});
vector<int>bit(coordinates.size()+1),answer(n);
int inserted=0;
for(const Query&query:queries){
while(inserted<m&&fish[inserted].first<=query.u){
int index=lower_bound(coordinates.begin(),coordinates.end(),fish[inserted].second)-
coordinates.begin()+1;
// Add this fish to all Fenwick ranges containing its coordinate.
for(int i=index;i<static_cast<int>(bit.size());i+=i&-i){
bit[i]++;
}
inserted++;
}
int count=upper_bound(coordinates.begin(),coordinates.end(),query.v)-coordinates.begin();
int total=0;
for(int i=count;i>0;i-=i&-i){
total+=bit[i];
}
answer[query.index]=total;
}
for(int i=0;i<n;i++){
if(i>0){
cout<<' ';
}
cout<<answer[i];
}
cout<<'\n';
}