A83458.地毯覆盖

普及-

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

有一块 N×NN\times N 的地板,行列均从 11 编号到 NN
接下来铺设 MM 张“地毯”,第 ii 张地毯给出一个矩形区域的两个角点坐标 (x1,y1)(x_1,y_1)(x2,y2)(x_2,y_2)(均为闭区间、包含边界),表示把该矩形范围内的所有格子都再覆盖一层。

请你输出最终每个格子被覆盖了多少次。

输入格式

第一行:两个整数 N,MN, M

接下来 MM 行:每行四个整数 x1,y1,x2,y2x_1, y_1, x_2, y_2,表示在矩形 [x1,x2]×[y1,y2][x_1, x_2]\times [y_1, y_2] 上覆盖一次。保证 1x1x2N1\le x_1\le x_2\le N1y1y2N1\le y_1\le y_2\le N

输出格式

输出 NN 行,每行 NN 个整数,用空格分隔,表示对应格子的被覆盖次数。

输入输出样例

  • 输入#1

    3 4
    1 1 2 2
    2 2 3 3
    1 3 1 3
    3 1 3 2
    

    输出#1

    1 1 1
    1 2 1
    1 2 1
    

说明/提示

  • 1N20001\le N\le 2000

  • 0M2×1050\le M\le 2\times 10^5

第 1 张:覆盖 (1,1)(2,2)(1,1)\sim(2,2),这是一块 2×22\times2 的矩形。

第 2 张:覆盖 (2,2)(3,3)(2,2)\sim(3,3)

第 3 张:只覆盖第 1 行第 3 列(一个点)。

第 4 张:覆盖第 3 行第 1~2 列。

叠加统计后得到上面的 3×3 结果。

首页