#CW63. 宝石劫案(jewels)

宝石劫案(jewels)

题目描述

平面上有 nn 颗位置互不相同的宝石,每颗宝石属于 kk 种颜色中的一种。第 jj 颗宝石的位置为 (xj,yj)(x_j,y_j),颜色为 cjc_j,其中颜色编号为 11 到 kk,并且每种颜色至少出现一次。

机械手只能抓取一次。它选择一条水平线段:设线段所在高度为 hh,左右端点的横坐标为 ll 和 rr,其中 l≤rl\le r。机械手会抓走所有同时满足 l≤xj≤rl\le x_j\le r 且 yj≤hy_j\le h 的宝石;在线段上、线段正下方以及更低位置的宝石都会被抓走,端点上的宝石也包含在内。

一次抓取是安全的,当且仅当被抓走的宝石所包含的颜色集合不是全部 kk 种颜色,也就是至少有一种颜色的宝石完全没有被抓走。请在所有可能的 l,r,hl,r,h 中,求一次安全抓取最多能得到的宝石数量。

输入格式

从 jewels.in 文件中读入。

第一行是测试组数 TT。每组数据先给出宝石数量 nn 和颜色种数 kk,随后给出 nn 行。第 jj 行包含 xj,yj,cjx_j,y_j,c_j,分别表示第 jj 颗宝石的横坐标、纵坐标和颜色编号。输入保证每种颜色至少有一颗宝石。

输出格式

从 jewels.out 文件中输出。

按测试组的输入顺序输出答案,每组一行一个整数,表示满足安全条件时一次抓取最多能得到的宝石数。

样例 1 输入

1
10 3
1 2 3
2 1 1
2 4 2
3 5 3
4 4 2
5 1 2
6 3 1
6 7 1
7 2 3
9 4 2

样例 1 输出

5

样例 1 解释

取 l=2l=2、r=6r=6、h=4h=4,被抓走的宝石为 (2,1,1)(2,1,1)、(2,4,2)(2,4,2)、(4,4,2)(4,4,2)、(5,1,2)(5,1,2)、(6,3,1)(6,3,1),共 55 颗,只包含颜色 1,21,2,缺少颜色 33,因此这次抓取是安全的。可以证明不存在能安全抓走 66 颗或更多宝石的方案。

数据范围

对全部数据,1≤T≤2001\le T\le 200。每组数据满足 2≤n≤2000002\le n\le 200000,2≤k≤n2\le k\le n,1≤xj,yj≤1091\le x_j,y_j\le 10^9,1≤cj≤k1\le c_j\le k,且每种颜色至少出现一次。另有总量限制 ∑n≤200000\sum n\le 200000。

本题采用子任务捆绑计分:一个子任务中的全部测试点均通过后,才能获得该子任务的分数。各子任务分数可以累加。

子任务 分值 测试点 附加条件
1 25 1∼51\sim 5 n≤30n\le 30
2 6∼106\sim 10 n≤200n\le 200
3 11∼1511\sim 15 n≤5000n\le 5000
4 16∼2016\sim 20 完整数据范围