6935.Sliding Window Minimum

Time Limit: 1s Memory Limit: 512MB

You are given an array of $n$ integers. Your task is to calculate the minimum of each window of $k$ elements, from left to right.

In this problem the input data is large and it is created using a generator.

Input Format(From the terminal/stdin)

The first line contains two integers $n$ and $k$ : the number of elements and the size of the window.

The next line contains four integers $x$ , $a$ , $b$ and $c$ : the input generator parameters. The input is generated as follows:

  • $x_1=x$
  • $x_i=(ax_{i-1}+b) \bmod c$ for $i=2,3,\dots,n$
  • $1 \le k \le n \le 10^7$
  • $0 \le x, a, b \le 10^9$
  • $1 \le c \le 10^9$

Output Format(To the terminal/stdout)

Print the xor of all window minimums.

Sample Input

Copy
8 5
3 7 1 11
 · \n
 · · ·  \n

Sample Output

Copy
3
 \n

The input array is $[3,0,1,8,2,4,7,6]$ . The windows are $[3,0,1,8,2]$ , $[0,1,8,2,4]$ , $[1,8,2,4,7]$ and $[8,2,4,7,6]$ , and their minimums are $0$ , $0$ , $1$ and $2$ . Thus, the answer is $0 \oplus 0 \oplus 1 \oplus 2 = 3$ .

Source: CSES, Sliding Window Problems, 3221

Submit

请先 登录

© 2025 FAQs