1215B.md (1193B)
1 Source: https://codeforces.com/problemset/problem/1215/B 2 3 B. The Number of Products 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 You are given a sequence $a_1, a_2, \dots, a_n$ consisting of $n$ non-zero integers (i.e. $a_i \ne 0$). 22 23 You have to calculate two following values: 24 25 1. the number of pairs of indices $(l, r)$ $(l \le r)$ such that $a_l \cdot a_{l + 1} \dots a_{r - 1} \cdot a_r$ is negative; 26 2. the number of pairs of indices $(l, r)$ $(l \le r)$ such that $a_l \cdot a_{l + 1} \dots a_{r - 1} \cdot a_r$ is positive; 27 28 Input 29 30 The first line contains one integer $n$ $(1 \le n \le 2 \cdot 10^{5})$ — the number of elements in the sequence. 31 32 The second line contains $n$ integers $a_1, a_2, \dots, a_n$ $(-10^{9} \le a_i \le 10^{9}; a_i \neq 0)$ — the elements of the sequence. 33 34 Output 35 36 Print two integers — the number of subsegments with negative product and the number of subsegments with positive product, respectively. 37 38 Examples 39 40 Input 41 42 ``` 43 5 44 5 -3 3 -1 1 45 ``` 46 47 Output 48 49 ``` 50 8 7 51 ``` 52 53 Input 54 55 ``` 56 10 57 4 2 -4 3 1 2 -4 3 2 3 58 ``` 59 60 Output 61 62 ``` 63 28 27 64 ``` 65 66 Input 67 68 ``` 69 5 70 -1 -2 -3 -4 -5 71 ``` 72 73 Output 74 75 ``` 76 9 6 77 ```