#P3356. [Usaco2004 Jan]禁闭围栏

    ID: 2545 传统题 1000ms 512MiB 尝试: 55 已通过: 25 难度: 5 上传者: 标签>CF1700普及+/提高-扫描线离散化差分树状数组同时事件分阶段处理Green

[Usaco2004 Jan]禁闭围栏

题目描述

贝茜又做犯事了,约翰打算关她禁闭。他的农场建有 NN 个矩形篱笆.围栏不重叠也互不接触,但足一个围栏可能包含一个或几个其他的围栏

他知道贝茜擅长逃脱,所以希望把她放在一个被围的层数最多的围栏里。请为他找出这样的围栏,并求出有多少个这样的围栏。

输入格式

第 11 行:一个整数 NN . 第 22 到 N+1N+1 行:每行四个整数 x1,y1,x2,y2x1, y1, x2, y2,表示围栏的左下角和右上角。

输出格式

两个整数:最大层数和几个这样的围栏.

4
1 1 16 16
6 6 11 13
7 7 9 12
3 3 10 5
3 1

数据范围与约定

对于 100%100\% 的数据,1≤N≤250000,1≤x,y≤109,x1<x2,y1<y21 ≤ N ≤ 250000, 1 ≤ x, y ≤ 10^9, x1<x2, y1< y2。

题目来源

Green