D. Destiny

Codeforces

IDCF840D

Time2000ms

Memory512MB

Difficulty—

data structuresprobabilities

English · Original

Chinese · Translation

Formal · Original

Once, Leha found in the left pocket an array consisting of _n_ integers, and in the right pocket _q_ queries of the form _l_ _r_ _k_. If there are queries, then they must be answered. Answer for the query is minimal _x_ such that _x_ occurs in the interval _l_ _r_ strictly more than times or - 1 if there is no such number. Help Leha with such a difficult task. ## Input First line of input data contains two integers _n_ and _q_ (1 ≤ _n_, _q_ ≤ 3·105) — number of elements in the array and number of queries respectively. Next line contains _n_ integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ _n_) — Leha's array. Each of next _q_ lines contains three integers _l_, _r_ and _k_ (1 ≤ _l_ ≤ _r_ ≤ _n_, 2 ≤ _k_ ≤ 5) — description of the queries. ## Output Output answer for each query in new line. [samples]

有一次，Leha 在左口袋发现了一个包含 $n$ 个整数的数组，在右口袋发现了一个包含 $q$ 个形如 $l$ $r$ $k$ 的查询。如果有查询，则必须回答。每个查询的答案是满足在区间 $[l, r]$ 中出现次数严格大于 $\frac{r - l + 1}{k}$ 次的最小的 $x$，如果不存在这样的数，则输出 $-1$。请帮助 Leha 解决这个难题。输入数据的第一行包含两个整数 $n$ 和 $q$（$1 ≤ n, q ≤ 3·10^5$）——数组的元素个数和查询个数。下一行包含 $n$ 个整数 $a_1, a_2, ..., a_n$（$1 ≤ a_i ≤ n$）——Leha 的数组。接下来的 $q$ 行每行包含三个整数 $l$, $r$ 和 $k$（$1 ≤ l ≤ r ≤ n$, $2 ≤ k ≤ 5$）——查询的描述。请在每行输出每个查询的答案。 ## Input 输入数据的第一行包含两个整数 $n$ 和 $q$（$1 ≤ n, q ≤ 3·10^5$）——数组的元素个数和查询个数。下一行包含 $n$ 个整数 $a_1, a_2, ..., a_n$（$1 ≤ a_i ≤ n$）——Leha 的数组。接下来的 $q$ 行每行包含三个整数 $l$, $r$ 和 $k$（$1 ≤ l ≤ r ≤ n$, $2 ≤ k ≤ 5$）——查询的描述。 ## Output 请在每行输出每个查询的答案。 [samples]

**Definitions** Let $ n, q \in \mathbb{Z}^+ $ denote the size of the array and number of queries, respectively. Let $ A = (a_1, a_2, \dots, a_n) $ be an array of integers where $ a_i \in \{1, 2, \dots, n\} $. For each query $ j \in \{1, \dots, q\} $, let $ (l_j, r_j, k_j) $ denote the query parameters, where $ 1 \le l_j \le r_j \le n $ and $ 2 \le k_j \le 5 $. **Constraints** 1. $ 1 \le n, q \le 3 \cdot 10^5 $ 2. $ 1 \le a_i \le n $ for all $ i \in \{1, \dots, n\} $ 3. For each query $ j $: - $ 1 \le l_j \le r_j \le n $ - $ 2 \le k_j \le 5 $ **Objective** For each query $ j $, define the subarray $ A_{[l_j, r_j]} = (a_{l_j}, a_{l_j+1}, \dots, a_{r_j}) $. Let $ f_j(x) $ denote the frequency of value $ x $ in $ A_{[l_j, r_j]} $. Compute: $$ \text{ans}_j = \min \left\{ x \in \mathbb{Z}^+ \mid f_j(x) > k_j \right\} $$ if such an $ x $ exists; otherwise, $ \text{ans}_j = -1 $.

Samples

Input #1

Output #1

1
-1

Input #2

Output #2

2
1
2

API Response (JSON)

{
  "problem": {
    "name": "D. Destiny",
    "description": {
      "content": "Once, Leha found in the left pocket an array consisting of _n_ integers, and in the right pocket _q_ queries of the form _l_ _r_ _k_. If there are queries, then they must be answered. Answer for the q",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF840D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Once, Leha found in the left pocket an array consisting of _n_ integers, and in the right pocket _q_ queries of the form _l_ _r_ _k_. If there are queries, then they must be answered. Answer for the q...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "有一次，Leha 在左口袋发现了一个包含 $n$ 个整数的数组，在右口袋发现了一个包含 $q$ 个形如 $l$ $r$ $k$ 的查询。如果有查询，则必须回答。每个查询的答案是满足在区间 $[l, r]$ 中出现次数严格大于 $\\frac{r - l + 1}{k}$ 次的最小的 $x$，如果不存在这样的数，则输出 $-1$。请帮助 Leha 解决这个难题。\n\n输入数据的第一行包含两个整数 $n$...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, q \\in \\mathbb{Z}^+ $ denote the size of the array and number of queries, respectively.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be an array of integers where $ a_i \\in \\{1, 2, \\...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments