D. Impressive Queries

Codeforces

IDCF10105D

Time10000ms

Memory64MB

Difficulty—

English · Original

Formal · Original

You are given two arrays, A and B, both of size N. You are given Q queries of the form (i, j, k). Where for each query, you have to find the cardinality of the multiset . First line contains two integers, N, and Q (1 ≤ N, Q ≤ 105). The next line contains N integers, the array A (1 ≤ Ai ≤ 109). The next line contains N integers, the array B (1 ≤ Bi ≤ 109). Each of the next Q lines contains three integers, i, j and k (1 ≤ i ≤ j ≤ N, 1 ≤ K ≤ 105), which represent a query as defined in the statement. Q lines, each containing the answer to one query. ## Input First line contains two integers, N, and Q (1 ≤ N, Q ≤ 105). The next line contains N integers, the array A (1 ≤ Ai ≤ 109). The next line contains N integers, the array B (1 ≤ Bi ≤ 109). Each of the next Q lines contains three integers, i, j and k (1 ≤ i ≤ j ≤ N, 1 ≤ K ≤ 105), which represent a query as defined in the statement. ## Output Q lines, each containing the answer to one query. [samples]

**Definitions** Let $ N, Q \in \mathbb{Z}^+ $. Let $ A = (a_1, a_2, \dots, a_N) $ and $ B = (b_1, b_2, \dots, b_N) $ be two arrays of integers. Let $ \mathcal{Q} = \{(i_q, j_q, k_q) \mid q \in \{1, \dots, Q\}\} $ be the set of queries. **Constraints** 1. $ 1 \leq N, Q \leq 10^5 $ 2. $ 1 \leq a_i, b_i \leq 10^9 $ for all $ i \in \{1, \dots, N\} $ 3. For each query $ q $: - $ 1 \leq i_q \leq j_q \leq N $ - $ 1 \leq k_q \leq 10^5 $ **Objective** For each query $ (i, j, k) \in \mathcal{Q} $, compute the cardinality of the multiset: $$ \{ a_\ell \mid \ell \in \{i, i+1, \dots, j\} \} \cap \{ b_\ell \mid \ell \in \{i, i+1, \dots, j\} \} $$ i.e., the number of elements that appear in both subarrays $ A[i:j] $ and $ B[i:j] $, counting multiplicities.

API Response (JSON)

{
  "problem": {
    "name": "D. Impressive Queries",
    "description": {
      "content": "You are given two arrays, A and B, both of size N. You are given Q queries of the form (i, j, k). Where for each query, you have to find the cardinality of the multiset . First line contains two inte",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 10000,
      "memory_limit": 65536
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10105D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given two arrays, A and B, both of size N. You are given Q queries of the form (i, j, k). Where for each query, you have to find the cardinality of the multiset .\n\nFirst line contains two inte...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N, Q \\in \\mathbb{Z}^+ $.  \nLet $ A = (a_1, a_2, \\dots, a_N) $ and $ B = (b_1, b_2, \\dots, b_N) $ be two arrays of integers.  \nLet $ \\mathcal{Q} = \\{(i_q, j_q, k_q) \\mid q \\in \\...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments