P2058 [NOIP 2016 普及组] 海港 提交答案加入题单复制题目 提交 173.79k 通过 60.83k 时间限制 1.00s 内存限制 125.00MB 题目编号 P2058 提供者 CCF_NOI 难度 普及/提高− 历史分数 暂无 来源 NOIP2016普及组自测 提交记录 查看题解 题目反馈 标签 NOIP 普及组 2016 相关讨论进入讨论版 推荐题目 复制 Markdown 中文 展开 进入 IDE 模式 题目背景 NOIP2016 普及组 T3

题目描述 小 K 是一个海港的海关工作人员，每天都有许多船只到达海港，船上通常有很多来自不同国家的乘客。

小 K 对这些到达海港的船只非常感兴趣，他按照时间记录下了到达海港的每一艘船只情况；对于第 i 艘到达的船，他记录了这艘船到达的时间 t i ​ (单位：秒)，船上的乘客数 k i ​ ，以及每名乘客的国籍 x i,1 ​ ,x i,2 ​ ,…,x i,k ​ 。

小K统计了 n 艘船的信息，希望你帮忙计算出以每一艘船到达时间为止的 24 小时（24 小时 =86400 秒）内所有乘船到达的乘客来自多少个不同的国家。

形式化地讲，你需要计算 n 条信息。对于输出的第 i 条信息，你需要统计满足 t i ​ −86400<t p ​ ≤t i ​ 的船只 p，在所有的 x p,j ​ 中，总共有多少个不同的数。

输入格式 第一行输入一个正整数 n，表示小 K 统计了 n 艘船的信息。

接下来 n 行，每行描述一艘船的信息：前两个整数 t i ​ 和 k i ​ 分别表示这艘船到达海港的时间和船上的乘客数量，接下来 k i ​ 个整数 x i,j ​ 表示船上乘客的国籍。

保证输入的 t i ​ 是递增的，单位是秒；表示从小K第一次上班开始计时，这艘船在第 t i ​ 秒到达海港。

保证 1≤n≤10 5 ，∑k i ​ ≤3×10 5 ，1≤x i,j ​ ≤10 5 ， 1≤t i−1 ​ ≤t i ​ ≤10 9 。

其中 ∑k i ​ 表示所有的 k i ​ 的和。

输出格式 输出 n 行，第 i 行输出一个整数表示第 i 艘船到达后的统计信息。

输入输出样例 输入 #1复制 3 1 4 4 1 2 2 2 2 2 3 10 1 3 输出 #1复制 3 4 4 输入 #2复制 4 1 4 1 2 2 3 3 2 2 3 86401 2 3 4 86402 1 5 输出 #2复制 3 3 3 4 说明/提示 【样例解释 1】

第一艘船在第 1 秒到达海港，最近 24 小时到达的船是第一艘船，共有 4 个乘客，分别是来自国家 4,1,2,2，共来自 3 个不同的国家；

第二艘船在第 2 秒到达海港，最近 24 小时到达的船是第一艘船和第二艘船，共有 4+2=6 个乘客，分别是来自国家 4,1,2,2,2,3，共来自 4 个不同的国家；

第三艘船在第 10 秒到达海港，最近 24 小时到达的船是第一艘船、第二艘船和第三艘船，共有 4+2+1=7 个乘客，分别是来自国家 4,1,2,2,2,3,3，共来自 4 个不同的国家。

【样例解释 2】

第一艘船在第 1 秒到达海港，最近 24 小时到达的船是第一艘船，共有 4 个乘客，分别是来自国家 1,2,2,3，共来自 3 个不同的国家。

第二艘船在第 3 秒到达海港，最近 24 小时到达的船是第一艘船和第二艘船，共有 4+2=6 个乘客，分别是来自国家 1,2,2,3,2,3，共来自 3 个不同的国家。

第三艘船在第 86401 秒到达海港，最近 24 小时到达的船是第二艘船和第三艘船，共有 2+2=4 个乘客，分别是来自国家 2,3,3,4，共来自 3 个不同的国家。

第四艘船在第 86402 秒到达海港，最近 24 小时到达的船是第二艘船、第三艘船和第四艘船，共有 2+2+1=5 个乘客，分别是来自国家 2,3,3,4,5，共来自 4个 不同的国家。

【数据范围】

对于 10% 的测试点，n=1,∑k i ​ ≤10,1≤x i,j ​ ≤10,1≤t i ​ ≤10。 对于 20% 的测试点，1≤n≤10,∑k i ​ ≤100,1≤x i,j ​ ≤100,1≤t i ​ ≤32767。 对于 40% 的测试点，1≤n≤100,∑k i ​ ≤100,1≤x i,j ​ ≤100,1≤t i ​ ≤86400。 对于 70% 的测试点，1≤n≤1000,∑k i ​ ≤3000,1≤x i,j ​ ≤1000,1≤t i ​ ≤10 9 。 对于 100% 的测试点，1≤n≤10 5 ,∑k i ​ ≤3×10 5 ,1≤x i,j ​ ≤10 5 ,1≤t i ​ ≤10 9 。