E. Simple sequence

Codeforces

IDCF10049E

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

You are given an array (s) of positive integers having the length n. Let's define the subarray as the array between some indexes l and r (l ≤ r and elements are sl, sl + 1, ..., sr). We call the subarray "simple" if mn is the minimal element in this subarray, mx is the maximal element in this subarray, a is a given parameter and inequality is satisfied. You need to find the size of the biggest possible simple subarray. The first line contains the number of test cases T (1 ≤ T ≤ 50). In the first line of every test case there are two integers n (1 ≤ n ≤ 105) and a (1 ≤ a ≤ 109) - the size of the array and the described parameter. In the second line of every test case there are n integers si (1 ≤ si ≤ 109) - the elements of the array. For each test case output one line containing “_Case #tc: size_” where tc is the number of the test case (starting from 1) and size is the size of the biggest possible simple subarray. ## Input The first line contains the number of test cases T (1 ≤ T ≤ 50).In the first line of every test case there are two integers n (1 ≤ n ≤ 105) and a (1 ≤ a ≤ 109) - the size of the array and the described parameter. In the second line of every test case there are n integers si (1 ≤ si ≤ 109) - the elements of the array. ## Output For each test case output one line containing “_Case #tc: size_” where tc is the number of the test case (starting from 1) and size is the size of the biggest possible simple subarray. [samples]

**Definitions** Let $ T $ be the number of test cases, $ T \leq 20 $. For each test case, let $ G = (V, E) $ be a binary tree with node set $ V $ and parent-child edges encoding left/right relationships. Each node $ v \in V $ has an associated key $ k_v \in \mathbb{R} $. **Constraints** 1. $ 1 \leq T \leq 20 $ 2. $ G $ is a binary tree: each node has at most two children (left and right). 3. Node keys are comparable real numbers. **Objective** Find the maximum cardinality of a subset $ S \subseteq V $ such that: - The induced subgraph on $ S $ is connected (in the tree sense), and - The subgraph formed by $ S $, with inherited left/right child relations and ancestor relationships, satisfies the binary search tree property: For every node $ v \in S $, all keys in the left subtree of $ v $ (within $ S $) are $ < k_v $, and all keys in the right subtree of $ v $ (within $ S $) are $ > k_v $. Output: $ \max |S| $ for each test case.

API Response (JSON)

{
  "problem": {
    "name": "E. Simple sequence",
    "description": {
      "content": "You are given an array (s) of positive integers having the length n. Let's define the subarray as the array between some indexes l and r (l ≤ r and elements are sl, sl + 1, ..., sr). We call the suba",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10049E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given an array (s) of positive integers having the length n.\n\nLet's define the subarray as the array between some indexes l and r (l ≤ r and elements are sl, sl + 1, ..., sr). We call the suba...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T $ be the number of test cases, $ T \\leq 20 $.  \nFor each test case, let $ G = (V, E) $ be a binary tree with node set $ V $ and parent-child edges encoding left/right relatio...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments