Algorithm
Problem Name: 2 AD-HOC - beecrowd | 2078
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2078
Green Peace! World Hypocrisy!
By XII Maratona de Programação IME-USP, 2008 
Brazil
Timelimit: 2
Albert Arnold Gore Jr is the full name of the former vice president of the United States, Al Gore, winner of the 2007 Nobel Peace Prize for his relentless work to educate the world's population to climate change caused by man. The documentary "An Inconvenient Truth" Oscar winner, shows the effects of global warming on the planet's landscape and predicts a catastrophic future for humanity is the tendency to usurp the resources of the planet is not changed.
Al Gore grew up in Washington DC since his father was a member and then a senator from Tennessee. He graduated from Harvard in 1969 and was an activist against the war in Vietnam and came to support the leader Martin Luther King in his fight against racial segregation. His role as vice president of the United States in the administration of Bill Clinton was also exceptional. Despite having had more votes than the competing Republican Party, lost the presidential election and walked away from the contest the presidency.
One of his most important works concerns the optimal positioning of furnaces in the production of bricks. The process of manufacture of bricks is very pollutant and requires high temperature firing of clay brick in order to reach the desired consistency. The burning consumes large quantities of wood produced on farms for this purpose. Studies of Harvard University show that there is a maximum distance for positioning these ovens: if too distant, heat radiation does not allow the burning is done equally, impairing the production of bricks and also the environment. Since the ovens are positioned in the forest (which is clipped to the burning), the distances are measured using the Manhattan metric, ie the distance between two points is given by the sum of the absolute values of the differences of coordinates. Your task is, given the location of various furnaces on a farm, and a distance D, determine, for each of ovens, furnaces are many distance at most D. With this information you can determine which furnaces need to be lit simultaneously without economic losses or environmental.
Input
The entrance is composed of several instances. The first line of input contains an integer T indicating the number of instances.
The first row in each instance has two integers N and D (1 ≤ N, D ≤ 100000) representing the number of ovens and distance, respectively. Each of the next N lines has two integers x and y (0 ≤ x, y ≤ 100000) indicating the position of an oven.
Output
For each instance print a line containing N integers which indicate how many ovens are distance at most D of the furnaces 1, 2, ..., N.
| Sample Input | Sample Output |
|
1 |
4 7 7 7 4 7 12 7 4 7 7 7 4 |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#define MAXN 200110
#define LSOne(S) (S & (-S))
using namespace std;
int bit[MAXN], resposta[MAXN], n, d;
void update(int pos, int val) {
while (pos < MAXN) {
bit[pos] += val;
pos += LSOne(pos);
}
}
int sum(int pos) {
pos = min(pos, MAXN - 1);
if (pos < = 0) return 0;
int answer = 0;
while (pos > 0) {
answer += bit[pos];
pos -= LSOne(pos);
}
return answer;
}
int query(int a, int b) { return sum(b) - sum(a - 1); }
struct point {
int x, y, id;
};
bool comp(point A, point B) {
if (A.x == B.x) return A.y < B.y;
return A.x < B.x;
}
int main() {
int TC;
scanf("%d", &TC);
while (TC--) {
scanf("%d %d", &n, &d);
memset(bit, 0, sizeof(bit));
vector < point> vetorzao;
for (int i = 0; i < n; i++) {
point davez;
int xi, yi;
scanf("%d %d", &xi, &yi);
// giramos 45 graus e fazemos a translacao no x para nao ficar
// negativo e no y para nao ficar nulo
davez.x = xi - yi + 100010;
davez.y = xi + yi + 1;
davez.id = i;
vetorzao.push_back(davez);
}
sort(vetorzao.begin(), vetorzao.end(), comp);
int ini = 0, fim = 0;
for (int i = 0; i < n; i++) {
while (ini < i && vetorzao[i].x - vetorzao[ini].x > d) {
update(vetorzao[ini++].y, -1);
}
while (fim < n && vetorzao[fim].x - vetorzao[i].x <= d) {
update(vetorzao[fim++].y, 1);
}
resposta[vetorzao[i].id] =
query(vetorzao[i].y - d, vetorzao[i].y + d);
}
for (int i = 0; i < n; i++) {
printf("%d ", resposta[i] - 1);
}
printf("\n");
}
return 0;
}
Input
13 2
0 2
1 3
1 2
1 1
2 4
2 3
2 2
2 1
2 0
3 3
3 2
3 1
4 2
Output