A183287.叠印方格

普及-

官方

通过率:0%

时间限制:1.00s

内存限制:256MB

题目描述

一张方格纸有 nn 行、mm 列,行从上到下编号为 11 到 nn,列从左到右编号为 11 到 mm。每个格子的初始盖印次数为 00。

Yuilice 盖了 qq 次印章。每次给出左上角格子 (r1,c1)(r_1,c_1) 和右下角格子 (r2,c2)(r_2,c_2),这两个角确定一个长方形范围。行号从 r1r_1 到 r2r_2、列号从 c1c_1 到 c2c_2 的所有格子都会被盖一次,包含四条边上的格子。重复盖印会累加次数。

请计算恰好被盖印 kk 次的格子数量,以及所有格子中最大的盖印次数。

输入格式

第一行包含四个整数 nn、mm、qq、kk,分别表示行数、列数、盖印次数和要统计的次数。

接下来 qq 行,每行包含四个整数 r1r_1、c1c_1、r2r_2、c2c_2,分别表示本次印章左上角和右下角格子的行列编号。

输出格式

输出两个整数,分别表示恰好盖印 kk 次的格子数量和最大盖印次数。

输入输出样例

  • 输入#1

    2 3 2 1
    1 1 2 2
    1 2 1 3
    

    输出#1

    4 2
    
  • 输入#2

    2 2 0 0
    

    输出#2

    4 0
    

说明/提示

样例 #1 解释

两次盖印后,各格次数为:

第1列 第2列 第3列
第1行 1 2 1
第2行 1 1 0

恰好盖印一次的格子有 44 个,最大盖印次数为 22。

数据范围

  • 1≤n,m≤401\le n,m\le40,0≤q≤400\le q\le40,0≤k≤q0\le k\le q。
  • 每次印章满足 1≤r1≤r2≤n1\le r_1\le r_2\le n,1≤c1≤c2≤m1\le c_1\le c_2\le m。
  • 如果 q=0q=0,输入中没有印章参数行。

输入解题思路,AI测评打分。不知道怎么写?

首页