codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

616D.md (1421B)


      1 Source: https://codeforces.com/problemset/problem/616/D
      2 
      3 D. Longest k-Good Segment
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 The array *a* with *n* integers is given. Let's call the sequence of one or more consecutive elements in *a* segment. Also let's call the segment k-good if it contains no more than *k* different values.
     22 
     23 Find any longest k-good segment.
     24 
     25 As the input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use scanf/printf instead of cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java.
     26 
     27 Input
     28 
     29 The first line contains two integers *n*, *k* (1 ≤ *k* ≤ *n* ≤ 5·105) — the number of elements in *a* and the parameter *k*.
     30 
     31 The second line contains *n* integers *a**i* (0 ≤ *a**i* ≤ 106) — the elements of the array *a*.
     32 
     33 Output
     34 
     35 Print two integers *l*, *r* (1 ≤ *l* ≤ *r* ≤ *n*) — the index of the left and the index of the right ends of some k-good longest segment. If there are several longest segments you can print any of them. The elements in *a* are numbered from 1 to *n* from left to right.
     36 
     37 Examples
     38 
     39 Input
     40 
     41 ```
     42 5 5  
     43 1 2 3 4 5
     44 ```
     45 
     46 Output
     47 
     48 ```
     49 1 5
     50 ```
     51 
     52 Input
     53 
     54 ```
     55 9 3  
     56 6 5 1 2 3 2 1 4 5
     57 ```
     58 
     59 Output
     60 
     61 ```
     62 3 7
     63 ```
     64 
     65 Input
     66 
     67 ```
     68 3 1  
     69 1 2 3
     70 ```
     71 
     72 Output
     73 
     74 ```
     75 1 1
     76 ```