COCI '15 Contest 3 #5 Nekameleoni

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 1.4s
Memory limit: 512M

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

Hey! I have an awesome task with chameleons, 5^{th} task for Saturday's competition.

Go ahead. . .

(...)

That's too difficult, I have an easier one, they won't even solve that one.

You are given an array of N integers from the interval [1,K]. You need to process M queries. The first type of query requires you to change a number in the array to a different value, and the second type of query requires you to determine the length of the shortest contiguous subarray of the current array that contains all numbers from 1 to K.

Hm, I can do it in \mathcal O(N^6). What's the limit for N?

Input Specification

The first line of input contains the integers N, K and M (1 \le N, M \le 100\,000, 1 \le K \le 50). The second line of input contains N integers separated by space, the integers from the array. After that, M queries follow, each in one of the following two forms:

  • 1 p v - change the value of the p^{th} number into v (1 \le p \le N, 1 \le v \le K)
  • 2 - what is the length of the shortest contiguous subarray of the array containing all the integers from 1 to K

In test cases worth 30% of total points, it will hold 1 \le N,M \le 5\,000.

Output Specification

The output must consist of the answers to the queries of the second type, each in its own line.

If the required subarray doesn't exist, output -1.

Sample Input 1

4 3 5
2 3 1 2
2
1 3 3
2
1 1 1
2

Sample Output 1

3
-1
4

Sample Input 2

6 3 6
1 2 3 2 1 1
2
1 2 1
2
1 4 1
1 6 2
2

Sample Output 2

3
3
4

Comments

There are no comments at the moment.