Uttered-Verified

Time limit3sMemory limit1024 MB

Summary

Given N houses in a circle and reports saying pairs of houses match or differ, count how many houses feel a contradiction after each report.

Level: Medium7 of 10
Topics: Union-find, Sliding window
Solved: No attempts yet

문제

A lake lies near the village of Cruzny. The village has $N$ houses, numbered 0 to $N-1$ in clockwise order.

When residents move in, each one receives an ecobag. Each house gets either a Hanbyeol ecobag or a Nikki ecobag. Through contact with one another, residents learn the ecobag types of $K$ consecutive houses in clockwise order, starting with their own. In other words, the resident of house $i$ knows the ecobag types of houses $i$ , $(i+1) \bmod N$ , ..., $(i+K-1) \bmod N$ .

The reporter Seonghun is covering the village news. Before reporting, Seonghun has collected the ecobag types of all $N$ houses. Each report is one of the following:

House $A$ received the same ecobag as house $B$ .
Houses $A$ and $B$ received different ecobag types.

Seonghun wants to test how false news changes the village, so he reports some items falsely. At first, residents know only limited information and cannot tell whether a report is false. As reports accumulate, some residents predict ecobag types from the reports and what they already know. They then find that no possible assignment fits, and they feel a contradiction. After that, they stop trusting Seonghun's news.

After each report, Seonghun wants to know how many houses feel a contradiction. Write a program that predicts the number of houses that feel a contradiction.

Examples1

Example 1
Input
```
2 1
0 1
1
2 0 1
```
Expected output
```
0
```