[COCI 2022/2023 #2] Lampice

Luogu

IDLGP9737

Time3000ms

Memory512MB

DifficultyP5

2022COCI（克罗地亚）

Teo 的阳台是一个长 $n+1$，宽 $m+1$ 的矩形平台，上有 $2k$ 盏彩灯，这些彩灯的颜色用 $1 \sim k$ 之间的一个数字来表示。每种颜色的彩灯都有 $2$ 盏，它们的坐标都为正整数。 Teo 认为阳台上一个区域是好的，当且仅当： - 这个小区域是矩形，且边都与阳台的边平行。 - 对于每一种颜色的 $2$ 盏彩灯，要么都在小区域内，要么都在小区域外。 - 小区域的左上角，右下角坐标均为整数。 - 小区域的长宽都**至少**为 $2$。现在，Teo 想请你求出在他的阳台上，有多少个小区域是好的。 **注意：左下角坐标为 $(0,0)$，右上角坐标为 $(n,m)$。** ## Input 第一行，三个整数 $n$，$m$，$k$（$1\le n\le150,1\le m\le1000,0\le k\le200000$），表示阳台的长，宽，和彩灯的颜色数。接下来 $k$ 行，每行 $4$ 个整数 $x_1$，$y_1$，$x_2$，$y_2$，第 $i$ 行表示颜色为 $i$ 的两盏彩灯的坐标。 ## Output 一行，一个整数，表示好的小区域个数。 [samples] ## Note |$\text{Subtask}$|分值|特殊性质| |:-:|:-:|:-:| |$1$|$26$|对于每种颜色的灯，$x_1=y_1=0$ |$2$|$12$|$n,m\le10$，$k\le1000$| |$3$|$35$|$m\le150$| |$4$|$37$|无| **本题满分 $110$ 分。**

Samples

Input #1

2 2 1
0 0 1 2

Output #1

Input #2

3 3 0

Output #2

Input #3

Output #3

API Response (JSON)

{
  "problem": {
    "name": "[COCI 2022/2023 #2] Lampice",
    "description": {
      "content": "Teo 的阳台是一个长 $n+1$，宽 $m+1$ 的矩形平台，上有 $2k$ 盏彩灯，这些彩灯的颜色用 $1 \\sim k$ 之间的一个数字来表示。每种颜色的彩灯都有 $2$ 盏，它们的坐标都为正整数。 Teo 认为阳台上一个区域是好的，当且仅当： - 这个小区域是矩形，且边都与阳台的边平行。 - 对于每一种颜色的 $2$ 盏彩灯，要么都在小区域内，要么都在小区域外。 - 小区域的左上角",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9737"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Teo 的阳台是一个长 $n+1$，宽 $m+1$ 的矩形平台，上有 $2k$ 盏彩灯，这些彩灯的颜色用 $1 \\sim k$ 之间的一个数字来表示。每种颜色的彩灯都有 $2$ 盏，它们的坐标都为正整数。\n\nTeo 认为阳台上一个区域是好的，当且仅当：\n\n- 这个小区域是矩形，且边都与阳台的边平行。\n\n- 对于每一种颜色的 $2$ 盏彩灯，要么都在小区域内，要么都在小区域外。\n\n- 小区域的左上角...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments