#LUOGUP1004. [NOIP2016 普及组] 海港
[NOIP2016 普及组] 海港
题目背景
NOIP2016 普及组 T3
题目描述
小 K 是一个海港的海关工作人员,每天都有许多船只到达海港,船上通常有很多来自不同国家的乘客。
小 K 对这些到达海港的船只非常感兴趣,他按照时间记录下了到达海港的每一艘船只情况;对于第 艘到达的船,他记录了这艘船到达的时间 (单位:秒),船上的乘客数 ,以及每名乘客的国籍 。
小K统计了 艘船的信息,希望你帮忙计算出以每一艘船到达时间为止的 小时( 小时 秒)内所有乘船到达的乘客来自多少个不同的国家。
形式化地讲,你需要计算 条信息。对于输出的第 条信息,你需要统计满足 的船只 ,在所有的 中,总共有多少个不同的数。
输入格式
第一行输入一个正整数 ,表示小 K 统计了 艘船的信息。
接下来 行,每行描述一艘船的信息:前两个整数 和 分别表示这艘船到达海港的时间和船上的乘客数量,接下来 个整数 表示船上乘客的国籍。
保证输入的 是递增的,单位是秒;表示从小K第一次上班开始计时,这艘船在第 秒到达海港。
保证 , ,, 。
其中 表示所有的 的和。
输出格式
输出 行,第 行输出一个整数表示第 艘船到达后的统计信息。
3
1 4 4 1 2 2
2 2 2 3
10 1 3
3
4
4
4
1 4 1 2 2 3
3 2 2 3
86401 2 3 4
86402 1 5
3
3
3
4
提示
【样例解释 1】
第一艘船在第 秒到达海港,最近 小时到达的船是第一艘船,共有 个乘客,分别是来自国家 ,共来自 个不同的国家;
第二艘船在第 秒到达海港,最近 小时到达的船是第一艘船和第二艘船,共有 个乘客,分别是来自国家 ,共来自 个不同的国家;
第三艘船在第 秒到达海港,最近 小时到达的船是第一艘船、第二艘船和第三艘船,共有 个乘客,分别是来自国家 ,共来自 个不同的国家。
【样例解释 2】
第一艘船在第 秒到达海港,最近 小时到达的船是第一艘船,共有 个乘客,分别是来自国家 ,共来自 个不同的国家。
第二艘船在第 秒到达海港,最近 小时到达的船是第一艘船和第二艘船,共有 个乘客,分别是来自国家 ,共来自 个不同的国家。
第三艘船在第 秒到达海港,最近 小时到达的船是第二艘船和第三艘船,共有 个乘客,分别是来自国家 ,共来自 个不同的国家。
第四艘船在第 秒到达海港,最近 小时到达的船是第二艘船、第三艘船和第四艘船,共有 个乘客,分别是来自国家 ,共来自 个 不同的国家。
【数据范围】
- 对于 的测试点,$n=1,\sum k_i \leq 10,1 \leq x_{i,j} \leq 10, 1 \leq t_i \leq 10$。
- 对于 的测试点,$1 \leq n \leq 10, \sum k_i \leq 100,1 \leq x_{i,j} \leq 100,1 \leq t_i \leq 32767$。
- 对于 的测试点,$1 \leq n \leq 100, \sum k_i \leq 100,1 \leq x_{i,j} \leq 100,1 \leq t_i \leq 86400$。
- 对于 的测试点,$1 \leq n \leq 1000, \sum k_i \leq 3000,1 \leq x_{i,j} \leq 1000,1 \leq t_i \leq 10^9$。
- 对于 的测试点,$1 \leq n \leq 10^5,\sum k_i \leq 3\times 10^5, 1 \leq x_{i,j} \leq 10^5,1\leq t_i \leq 10^9$。