codeforces-scrape

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

1426D.md (2223B)


      1 Source: https://codeforces.com/problemset/problem/1426/D
      2 
      3 D. Non-zero Segments
      4 
      5 time limit per test
      6 
      7 2 seconds
      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 Kolya got an integer array $a_1, a_2, \dots, a_n$. The array can contain both positive and negative integers, but Kolya doesn't like $0$, so the array doesn't contain any zeros.
     22 
     23 Kolya doesn't like that the sum of some subsegments of his array can be $0$. The subsegment is some consecutive segment of elements of the array.
     24 
     25 You have to help Kolya and change his array in such a way that it doesn't contain any subsegments with the sum $0$. To reach this goal, you can insert any integers between any pair of adjacent elements of the array (integers can be really any: positive, negative, $0$, any by absolute value, even such a huge that they can't be represented in most standard programming languages).
     26 
     27 Your task is to find the minimum number of integers you have to insert into Kolya's array in such a way that the resulting array doesn't contain any subsegments with the sum $0$.
     28 
     29 Input
     30 
     31 The first line of the input contains one integer $n$ ($2 \le n \le 200\,000$) — the number of elements in Kolya's array.
     32 
     33 The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($-10^{9} \le a_i \le 10^{9}, a_i \neq 0$) — the description of Kolya's array.
     34 
     35 Output
     36 
     37 Print the minimum number of integers you have to insert into Kolya's array in such a way that the resulting array doesn't contain any subsegments with the sum $0$.
     38 
     39 Examples
     40 
     41 Input
     42 
     43 ```
     44 4
     45 1 -5 3 2
     46 ```
     47 
     48 Output
     49 
     50 ```
     51 1
     52 ```
     53 
     54 Input
     55 
     56 ```
     57 5
     58 4 -2 3 -9 2
     59 ```
     60 
     61 Output
     62 
     63 ```
     64 0
     65 ```
     66 
     67 Input
     68 
     69 ```
     70 9
     71 -1 1 -1 1 -1 1 1 -1 -1
     72 ```
     73 
     74 Output
     75 
     76 ```
     77 6
     78 ```
     79 
     80 Input
     81 
     82 ```
     83 8
     84 16 -5 -11 -15 10 5 4 -4
     85 ```
     86 
     87 Output
     88 
     89 ```
     90 3
     91 ```
     92 
     93 Note
     94 
     95 Consider the first example. There is only one subsegment with the sum $0$. It starts in the second element and ends in the fourth element. It's enough to insert one element so the array doesn't contain any subsegments with the sum equal to zero. For example, it is possible to insert the integer $1$ between second and third elements of the array.
     96 
     97 There are no subsegments having sum $0$ in the second example so you don't need to do anything.