最新消息:

信息学奥赛题库- 【16NOIP普及组】海港

C++ 少儿编程 1047浏览 0评论

【题目描述】

小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≥1,sum k_i ≤3×10^5,1≤x_{i,j}≤10^5,1≤t_{i-1}<t_i≤10^9$。

其中$sum k_i$表示所有的$k_i$的和,$sum k_i=k_1+k_2+…+k_n$。

【输出】

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

【输入样例】

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

【输出样例】

3
4
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】

4
1 4 1 2 2 3
3 2 2 3
86401 2 3 4
86402 1 5

【样例输出2】

3
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$个不同的国家;

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

【子任务】

对于10%的测试点,$n=1,sum k_i≤10,1≤x_{i,j}≤10,1≤t_i≤10$;

对于20%的测试点,$1≤n≤10,sum k_i≤100,1≤x_{i,j}≤100,1≤t_i≤32767$;

对于40%的测试点,$1≤n≤100,sum k_i≤100,1≤x_{i,j}≤100,1≤t_i≤86400$;

对于70%的测试点,$1≤n≤1000,sum k_i≤3000,1≤x_{i,j}≤1000,1≤t_i≤10^9$;

对于100%的测试点,$1≤n≤10^5,sum k_i≤3×10^5,1≤x_{i,j}≤10^5,1≤t_i≤10^9$。

您必须 登录 才能发表评论!