Fishing Problem ! - Algorithm

Problem

             f

  f       f      f    f

       f      f    f

  ----------------------

x .  .  .   .  .    .

f represents a fish and . represents a person who does fishing. These people are on a line that we call x. A fisherman can only capture a fish at a k distance of the fish or less (distance, Mahattan distance). Exemple :

Input

4 5 10

3 1 2 4 5

1 2

2 3

1 1

2 5

Output

4 4 4 4 4

Explanation of exemple

The first integer represents the number of fish, the second integer represents the number of fisherman and the third number is k. Then we have the position of the fishman. After you have the coordinates of the fish.

Constraints

Time : 0.5 second

Memory : 50000 ko 

The x coordinate of a fish is always <= 1000, no matter the subtask.

The y coordinate of a fish is always <= 1000, no matter the subtask.

Subtasks (in total 100 pts):

- number of fish < 100 and number of fishman < 100 - 20 pts

- number of fish < 1000 and number of fishman < 1000 - 20 pts
- number of fish < 1000 and number of fishman < 10000 - 20 pts
- number of fish < 1000000 and number of fishman < 1000 - 20 pts
- number of fish < 1000000 and number of fishman < 10000 - 20 pts

Analyse

This problem can be easily solved in O(nbFish*nbFishman) by looping on all the fisherman and all the fish. There exists a solution much faster in almost O(nbFish * log(nbFish)) + a sort. Here is the C++ code :

#include <iostream>

#include <algorithm>

#include <deque>

#include <queue>

#include <vector>

#include <map>

using namespace std;

int main(){

ios::sync_with_stdio(false);

cin.tie(nullptr);

int n,m,l;

cin >> n >> m >> l;

deque<pair<int,int>> v;

for (int i=0; i<n; ++i){

int a,b;

cin >> a >> b;

if (b > l) continue;

v.emplace_back(a-(l-b),a+(l-b));

}

sort(v.begin(),v.end());

deque<int> pecheurs(m);

for (int i=0; i<m; ++i) cin >> pecheurs[i];

deque<int> ordre_init=pecheurs;

sort(pecheurs.begin(),pecheurs.end());

priority_queue<int,vector<int>,greater<int>> q;

map<int,int> print;

int ret=0;

while (!v.empty() and !pecheurs.empty()){

while (!pecheurs.empty() and v[0].first > pecheurs[0]){

while (!q.empty() and q.top() < pecheurs[0]){

q.pop();

--ret;

}

print[pecheurs[0]]=ret;

pecheurs.pop_front();

}

q.emplace(v[0].second);

++ret;

v.pop_front();

}

while (!pecheurs.empty()){

while (!q.empty() and q.top() < pecheurs[0]){

q.pop();

--ret;

}

print[pecheurs[0]]=ret;

pecheurs.pop_front();

}

for (auto& i:ordre_init) cout << print[i] << '\n';

return 0;

}