P17134 [KOI 2026 #1] Neighbors

In KOI Village, there is a straight road. There are a total of $N$ houses on the road. $N$ students numbered from $1$ to $N$ live in these houses, with exactly one student in each house. For an integer $i$ ($1 \le i \le N$), the coordinate of the house where student $i$ lives is $i$. That is, the coordinate of student $1$’s house is $1$, and the coordinate of student $N$’s house is $N$. There are two schools in KOI Village, called School $1$ and School $2$. Each student attends exactly one of these two schools. For students $i$ and $j$ ($i \ne j$), if at least one of the following conditions holds, then the two students are said to be neighbors of each other: - The two students attend the same school, and the distance between their houses is at most $K_1$. - The two students attend different schools, and the distance between their houses is at most $K_2$. Here, the distance between two different houses is defined as the larger coordinate minus the smaller coordinate. For example, the distance between the house where student $3$ lives and the house where student $5$ lives is $5-3=2$. Write a program to compute, for each student, the number of students who are neighbors with them. Note that a student is not considered their own neighbor.

The first line contains three integers $N$, $K_1$, and $K_2$, separated by spaces. The second line contains $N$ integers $S_1,S_2,\ldots,S_N$, separated by spaces. Here, $S_i$ is the index of the school that student $i$ attends ($1 \le i \le N$).

Output one line containing $N$ integers separated by spaces. The $i$-th integer is the number of students who are neighbors with student $i$ ($1 \le i \le N$).

### Constraints - All numbers in the input are integers. - $2 \le N \le 3\,000$. - $1 \le K_1,K_2 \le N-1$. - For each integer $i$ ($1 \le i \le N$), $1 \le S_i \le 2$. ### Subtasks | Subtask | Points | Additional Constraints | |---|---:|---| | $1$ | $5$ | $N=2$。 | | $2$ | $25$ | $K_1=K_2=1$。 | | $3$ | $35$ | $S_1=S_2=\cdots=S_N=1$。 | | $4$ | $35$ | No additional constraints. | Translated by ChatGPT-5.6. Translated by ChatGPT 5