Wesley's Anger Contest 6 Problem 2 - Cheap Christmas Lights

View as PDF

Submit solution


Points: 5 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Now that Christmas is over, Wesley needs to take down his Christmas lights! He has a line of N lights, some of which may be on, and Wesley needs all the lights to be off before he can unplug them (or else he'll receive a deadly electrical shock). Each light has a corresponding switch that can be used to turn the light on or off, and Wesley can use at most one of these switches every second, starting from the 1^\text{st} second. However, these lights are finicky, and in the next M seconds they will toggle their state on their own! Specifically, during the i^\text{th} second the {b_i}^\text{th} light will flip its state. Wesley wants to take the lights down as soon as possible, so he would like to know what's the earliest time possible for all the lights to be off, assuming he uses switches in an ideal manner. In particular, output the least i such that all lights can be turned off by the end of the i^\text{th} second by some sequence of switch usages. Note if all lights are initially off, then the least such i is 0.

Constraints

For this problem, you will be required to pass all the samples in order to receive any points. In addition, you must pass all previous subtasks to earn points for a specific subtask.

For all subtasks:

1 \le N,M \le 200\,000
a_i \in \{0,1\} for all 1 \le i \le N
1 \le b_i \le N for all 1 \le i \le M

Subtask 1 [15%]

1 \le N, M \le 5\,000

Subtask 2 [85%]

No additional constraints.

Input Specification

On the first line will be two integers N and M, the number of lights and the number of unsolicited changes the lights will make.

The second line will contain N integers a_1, a_2, \dots, a_N, the initial state of the lights. a_i = 1 indicates that the i^\text{th} light is initially on, otherwise off.

The third and final line will contain M integers b_1, b_2, \dots, b_M, which denotes that the {b_i}^\text{th} light is toggled on/off during the i^\text{th} second.

Output Specification

This problem is graded with an identical checker. This includes whitespace characters. Ensure that every line of output is terminated with a \n character and that there are no trailing spaces.

Output a single integer, the earliest time (in seconds) it will take for Wesley to turn all the lights off. Note that if all the lights can be turned off before M seconds have passed, Wesley will ignore any future toggles and take them down immediately.

Sample Input 1

3 3
1 1 1
1 2 3

Sample Output 1

2

Sample Input 2

5 8
0 1 0 1 1
1 2 2 1 4 3 2 1

Sample Output 2

4

Comments

There are no comments at the moment.