AT_abc304_d.[ABC304D] A Piece of Cake

普及+/提高

通过率:0%

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

在 xyxy 平面上,一块带有一些草莓的蛋糕占据了一块矩形区域 {(x,y):0≤x≤W,0≤y≤H}\{(x,y):0\le x\le W,0\le y\le H\}。

蛋糕上有 NN 个草莓,第 ii 个草莓的坐标是 (pi,qi)(p_i,q_i)。现在,高桥要用小刀按照以下规则将蛋糕切成小块。

  • 首先,沿着平行于 yy 轴的 AA 条直线:直线 x=a1x=a_1、直线 x=a2x=a_2、……、直线 x=aAx=a_A,将蛋糕切开。
  • 接着,沿着平行于 xx 轴的 YY 条直线:直线 y=b1y=b_1、直线 y=b2y=b_2、……、直线 y=bBy=b_B,将蛋糕切开。

到了最后,蛋糕会被切成 (A+1)(B+1)(A+1)(B+1) 块长方形,现在高桥要选择其中一块,求他选择的蛋糕上草莓个数可能的最大值和最小值。

保证切割的边缘线上没有草莓,具体请参照数据范围。

输入格式

输入共 (N+6)(N+6) 行。

第一行两个整数 W,HW,H。

第二行一个整数 NN。

第 3∼N+23\sim N+2 行,第 i+2i+2 行两个整数 pi,qip_i,q_i。

第 N+3N+3 行,一个整数 AA。

接下来一行 AA 个整数 a1,a2,⋯ ,aAa_1,a_2,\cdots,a_A。

第 N+5N+5 行,一个整数 BB。

接下来一行 BB 个整数 b1,b2,⋯ ,bBb_1,b_2,\cdots,b_B。

以上变量含义均参考题意。

输出格式

共一行用空格隔开的两个整数,第一个表示可能的最少的草莓数量,第二个表示可能的最多的草莓数量。

输入输出样例

  • 输入#1

    7 6
    5
    6 1
    3 1
    4 2
    1 5
    6 2
    2
    2 5
    2
    3 4

    输出#1

    0 2
  • 输入#2

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

    输出#2

    1 1

说明/提示

  • 3≤W,H≤1093 \le W, H \le 10^9
  • 1≤N≤2×1051 \le N \le 2 \times 10^5
  • 0<pi<W0 < p_i < W
  • 0<qi<H0 < q_i < H
  • i≠j  ⟹  (pi,qi)≠(pj,qj)i \ne j \implies (p_i, q_i) \ne (p_j, q_j)
  • 1≤A,B≤2×1051 \le A, B \le 2 \times 10^5
  • 0<a1<a2<⋯<aA<W0 < a_1 < a_2 <\cdots < a_A < W
  • 0<b1<b2<⋯<bB<H0 \lt b_1 \lt b_2 \lt \cdots \lt b_B \lt H
  • pi∉{a1,a2,…,aA}p_i \notin \{ a_1, a_2, \ldots, a_A \}
  • qi∉{b1,b2,…,bB}q_i \notin \{ b_1, b_2, \ldots, b_B \}
  • 所有输入的值都是正整数。

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

首页