『SpOI - R1』Double Champions

Luogu

IDLGP10793

Time1250ms

Memory512MB

DifficultyP4

动态规划 DP贪心单调队列O2优化排序

**本题包含多组数据。** 现在有若干个格子排在一行上。再给出 $n$ 个区间，每个区间 $i$ 可以覆盖 $[l_i,r_i]$ 这个区间中的每一个格子（例如，区间 $[1,2]$ 可以覆盖格子 $1,2$）。现在需要把这些区间分组，每个组带来的贡献为所有其旗下的区间的交的总长度。你需要求出最少把这些区间分成多少组，才能使得每一组的贡献都 $\geq w$。如果不存在任何方案满足条件，输出 `No`。 ## Input 第一行一个整数 $T$，表示数据组数。对于每组数据，第一行两个整数 $n,w$。接下来 $n$ 行，每一行两个整数 $l_i,r_i$，描述一个区间。 ## Output 对于每组数据，输出一行一个答案，表示最少要分的组数，或者字符串 `No`，表示无解。 [samples] ## Note #### 样例 #1 解释按照输入顺序将输入的区间依次编号为 $①,②,③,④,⑤$。可以将 $5$ 个区间分为以下 $3$ 组：$\{①,④\},\{②\},\{③⑤\}$。这样每一组的贡献即交集大小分别为 $3,3,3$，符合对每组贡献 $\geq 3$ 的要求。可以证明，$3$ 组是所有符合条件的区间划分方案中组数最少的。 ### 数据范围 **请注意常数因子对程序效率的影响。** **本题开启捆绑测试和子任务依赖。** 对于 $100\%$ 的数据，$1\leq T\leq 20$，$1\leq n\leq 2\times 10^5$，$0\leq w\leq 10^6$，$1\leq l_i\leq r_i\leq 10^6$。 | Subtask | $n\leq$ | $w,l_i,r_i\leq$ | 得分 | 子任务依赖 | | :----------: | :----------: | :----------: | :----------: | :----------: | | 1 | $8$ | $15$ | $10$ | 无 | | 2 | $11$ | $20$ | $10$ | 1 | | 3 | $1.5\times 10^3$ | $10^4$ | $25$ | 1,2 | | 4 | $2\times 10^5$ | $10^6$ | $55$ | 1,2,3 |

Samples

Input #1

Output #1

3
3

API Response (JSON)

{
  "problem": {
    "name": "『SpOI - R1』Double Champions",
    "description": {
      "content": "**本题包含多组数据。** 现在有若干个格子排在一行上。 再给出 $n$ 个区间，每个区间 $i$ 可以覆盖 $[l_i,r_i]$ 这个区间中的每一个格子（例如，区间 $[1,2]$ 可以覆盖格子 $1,2$）。 现在需要把这些区间分组，每个组带来的贡献为所有其旗下的区间的交的总长度。 你需要求出最少把这些区间分成多少组，才能使得每一组的贡献都 $\\geq w$。如果不存在任何方案满足条",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1250,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10793"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "**本题包含多组数据。**\n\n现在有若干个格子排在一行上。\n\n再给出 $n$ 个区间，每个区间 $i$ 可以覆盖 $[l_i,r_i]$ 这个区间中的每一个格子（例如，区间 $[1,2]$ 可以覆盖格子 $1,2$）。\n\n现在需要把这些区间分组，每个组带来的贡献为所有其旗下的区间的交的总长度。\n\n你需要求出最少把这些区间分成多少组，才能使得每一组的贡献都 $\\geq w$。如果不存在任何方案满足条...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments