H. Count Subarrays

Codeforces

IDCF10058H

Time1000ms

Memory512MB

Difficulty—

English · Original

Formal · Original

Given an array of N integers A1, A2 ... AN and an integer K, count number of subarrays of A such that number of inversions in those subarrays is at least K. Inversions in a subarray Ai, Ai + 1,..., Aj is defined as number of pairs (a, b) such that i ≤ a < b ≤ j and Aa > Ab. First line consists of N and K in single line. Next line contains N space separated integers denoting array A. Print the required answer in one line. *Constraints* Let’s denote by A[i, j] the subarray Ai, Ai + 1 ... Aj. Example 1. A[1, 4, A[2, 4], A[3, 4]] have at least 1 inversion. Example 2. All subarrays are valid. ## Input First line consists of N and K in single line. Next line contains N space separated integers denoting array A. ## Output Print the required answer in one line.*Constraints* 1 ≤ N ≤ 105 0 ≤ Ai ≤ 109 0 ≤ K ≤ N * (N - 1) / 2 [samples] ## Note Let’s denote by A[i, j] the subarray Ai, Ai + 1 ... Aj.Example 1. A[1, 4, A[2, 4], A[3, 4]] have at least 1 inversion.Example 2. All subarrays are valid.

**Definitions** Let $ N, K \in \mathbb{Z}^+ $. Let $ A = (A_1, A_2, \dots, A_N) $ be a sequence of integers. For a subarray $ A[i,j] = (A_i, A_{i+1}, \dots, A_j) $ with $ 1 \leq i \leq j \leq N $, define the number of inversions as: $$ \text{inv}(i,j) = \left| \left\{ (a,b) \mid i \leq a < b \leq j \text{ and } A_a > A_b \right\} \right| $$ **Constraints** 1. $ 1 \leq N \leq \text{some upper bound (not specified)} $ 2. $ 1 \leq K \leq \binom{N}{2} $ 3. $ A_i \in \mathbb{Z} $ for all $ i \in \{1, \dots, N\} $ **Objective** Count the number of subarrays $ A[i,j] $ such that: $$ \text{inv}(i,j) \geq K $$

API Response (JSON)

{
  "problem": {
    "name": "H. Count Subarrays",
    "description": {
      "content": "Given an array of N integers A1, A2 ... AN and an integer K, count number of subarrays of A such that number of inversions in those subarrays is at least K. Inversions in a subarray Ai, Ai + 1,..., A",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10058H"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Given an array of N integers A1, A2 ... AN and an integer K, count number of subarrays of A such that number of inversions in those subarrays is at least K.\n\nInversions in a subarray Ai, Ai + 1,..., A...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N, K \\in \\mathbb{Z}^+ $.  \nLet $ A = (A_1, A_2, \\dots, A_N) $ be a sequence of integers.  \nFor a subarray $ A[i,j] = (A_i, A_{i+1}, \\dots, A_j) $ with $ 1 \\leq i \\leq j \\leq N ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments