「DBOI」Round 1 三班不一般

Luogu

IDLGP9400

Time1000ms

Memory256MB

DifficultyP5

动态规划 DP线段树O2优化

HQ 需要管理 $n$ 个宿舍的灯，第 $i$ 个宿舍的同学因为有着传奇颜值而十分挑剔，只能忍受亮度为 $[l_i,r_i]$ 的灯。每个宿舍的灯的亮度可以在对应的可忍受范围内肆意调节。今天陈添润决定成为总司令，对所有宿舍的灯进行调节，为了防止被 HQ 当场抓捕，他不能让 HQ 发觉宿舍的灯太过刺眼，当连续 $a$ 个宿舍的灯亮都大于 $b$ 的时候，宿舍的灯就刺眼了。$\color{white}\text{不可以，总司令}$ 因此，帮助陈添润数一数一共有多少灯泡调节方案能满足宿舍不刺眼，答案对 $998244353$ 取模。 ## Input 第一行是三个正整数 $n,a,b$，含义如题所示。下面一共 $n$ 行，每行两个正整数，第 $i$ 行的两个正整数分别表示 $l_i,r_i$。 ## Output 一行一个整数，表示答案，对 $998244353$ 取模。 [samples] ## Background HQ 是传奇颜值中学的一位尽职尽责的后勤部教师，同时也是宿舍的管理成员，负责管理开关灯。对于他来说，最令人厌烦的的就是极不一般的三班的一群猴子乱玩自己宿舍和别人宿舍的灯，但是却没法当场发现并抓捕始作俑者。 ## Note ### 样例解释对于样例 $1$，只有两种方案： $\{3,3,2\}$ 或者 $\{3,3,3\}$ 能满足条件。对于样例 $3$，请将答案对 $998244353$ 取模。 ### 数据范围 **本题采用捆绑测试。** 对于所有数据，满足 $1\le n\le 2\cdot 10^5$，$1\le a\le n+1$，$1\le b\le 10^9$，$1\le l_i\le r_i\le 10^9$。 | $\textrm{Subtask}$ | $n,(a-1)\le$ | $l_i,r_i,b\le$ | 特殊性质 | 分值 | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $5$ | $20$ | 无 | $10$ | | $2$ | $2\cdot 10^5$ | $10^9$ | $a=n+1$ | $10$ | | $3$ | $2\cdot 10^5$ | $10^9$ | $a=1$ | $10$ | | $4$ | $10^3$ | $10^9$ | 无 | $30$ | | $5$ | $2\cdot 10^5$ | $10^9$ | 无 | $40$ |

Samples

Input #1

Output #1

Input #2

Output #2

Input #3

Output #3

358014651

API Response (JSON)

{
  "problem": {
    "name": "「DBOI」Round 1 三班不一般",
    "description": {
      "content": "HQ 需要管理 $n$ 个宿舍的灯，第 $i$ 个宿舍的同学因为有着传奇颜值而十分挑剔，只能忍受亮度为 $[l_i,r_i]$ 的灯。每个宿舍的灯的亮度可以在对应的可忍受范围内肆意调节。 今天陈添润决定成为总司令，对所有宿舍的灯进行调节，为了防止被 HQ 当场抓捕，他不能让 HQ 发觉宿舍的灯太过刺眼，当连续 $a$ 个宿舍的灯亮都大于 $b$ 的时候，宿舍的灯就刺眼了。$\\color{whit",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9400"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "HQ 需要管理 $n$ 个宿舍的灯，第 $i$ 个宿舍的同学因为有着传奇颜值而十分挑剔，只能忍受亮度为 $[l_i,r_i]$ 的灯。每个宿舍的灯的亮度可以在对应的可忍受范围内肆意调节。\n\n今天陈添润决定成为总司令，对所有宿舍的灯进行调节，为了防止被 HQ 当场抓捕，他不能让 HQ 发觉宿舍的灯太过刺眼，当连续 $a$ 个宿舍的灯亮都大于 $b$ 的时候，宿舍的灯就刺眼了。$\\color{whit...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments