K. Candies

Codeforces

IDCF10230K

Time4000ms

Memory1024MB

Difficulty—

English · Original

Formal · Original

Nicoleta received a box of candies from his sister. It has a rectangular shape with dimensions $1$ x $N$ and contains $N$ candies, and each one has a value $C_i$ of deliciousness. Sanchola lives with Nicoleta in Revuocnav and he loves to make Nicoleta upset. Sanchola found out about the gift and decided to take a consecutive subsequence of candies from the box when Nicoleta is not looking. The total deliciousness taken by Sanchola should be at least L so that he can enjoy the candies, but not greater than R, to not raise suspicion. Sanchola needs your help to calculate the number of distinct consecutive subsequences that he can take from Nicoleta. Two consecutive subsequences $C_{l_1} \\\\cdots C_{r_1}$ and $C_{l_2} \\\\cdots C_{r_2}$ are considered equal if and only if they have the same number of candies $x$ and $forall k$ $C_{l_1 + k} = C_{l_2 + k}, 0 <= k < x$. The first line consists of three integers $N$ $(1 <= N <= 5 * 10^5)$, $L$ and $R$ $(-10^(18) <= L <= R <= 10^(18))$ . The second line contains $N$ integers $C_1, C_2, \\\\cdots, C_n$ ($-10^9 <= a_i <= 10^9$), indicating the deliciousness of each candy. Output a single integer - The number of distinct consecutive subsequences whose sum is between $L$ and $R$. ## Input The first line consists of three integers $N$ $(1 <= N <= 5 * 10^5)$, $L$ and $R$ $(-10^(18) <= L <= R <= 10^(18))$ .The second line contains $N$ integers $C_1, C_2, \\\\cdots, C_n$ ($-10^9 <= a_i <= 10^9$), indicating the deliciousness of each candy. ## Output Output a single integer - The number of distinct consecutive subsequences whose sum is between $L$ and $R$. [samples]

**Definitions** Let $ F_k $ denote the $ k $-th Fibonacci number, defined by: $ F_1 = 1 $, $ F_2 = 1 $, and $ F_{k+2} = F_{k+1} + F_k $ for $ k \geq 1 $. Let $ n \in \mathbb{Z}^+ $ be given. Consider the set $ S_n = \{ F_1, F_2, \dots, F_n \} $. **Constraints** $ 1 \leq n \leq 10^5 $ **Objective** Count the number of unordered pairs $ \{x, y\} \subseteq S_n $ with $ x \ne y $ such that $ \gcd(x, y) = 1 $.

API Response (JSON)

{
  "problem": {
    "name": "K. Candies",
    "description": {
      "content": "Nicoleta received a box of candies from his sister. It has a rectangular shape with dimensions $1$ x $N$ and contains $N$ candies, and each one has a value $C_i$ of deliciousness. Sanchola lives with",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 1048576
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10230K"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Nicoleta received a box of candies from his sister. It has a rectangular shape with dimensions $1$ x $N$ and contains $N$ candies, and each one has a value $C_i$ of deliciousness.\n\nSanchola lives with...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ F_k $ denote the $ k $-th Fibonacci number, defined by:  \n$ F_1 = 1 $, $ F_2 = 1 $, and $ F_{k+2} = F_{k+1} + F_k $ for $ k \\geq 1 $.  \n\nLet $ n \\in \\mathbb{Z}^+ $ be given. Co...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments