Lie
Time limit2sMemory limit128 MB
Detect the first parity query in a sequence that becomes inconsistent with earlier ones, using weighted union-find over prefix-sum parities.
- Level
Medium6 of 10
- Topics
- Union-find, Bit manipulation, Prefix sum
- Solved
- No attempts yet
Problem
Two people are playing a game as a questioner and an answerer. The answerer is given a binary sequence of length N, where 1 ≤ N ≤ 1,000,000,000.
The questioner asks M questions, where 1 ≤ M ≤ 5,000. Each question asks whether the number of ones in the inclusive interval from position i to position j is even or odd. The answerer replies 0 if the count is even and 1 if the count is odd.
Given the questions and answers in order, find the first question at which the answers can no longer all be true at the same time.
Saying that the answerer lied on a question means that no binary sequence exists that satisfies every previous answer together with that answer.
Input
The first line contains two integers N and M. Each of the next M lines contains three integers i, j, and a describing one question. The value a is the answer: 0 means the number of ones in the interval is even, and 1 means it is odd.
Output
Print the number of the first question on which the answerer lied. If none of the answers contradict the earlier answers, print M+1.