NOIP2016 普及組第三題 海港

瘋狂的函數 2022-01-07 20:31:03 阅读数:312

noip2016 noip 普及 第三 海港

題目描述

小K是一個海港的海關工作人員,每天都有許多船只到達海港,船上通常有很多來自不同國家的乘客。

小K對這些到達海港的船只非常感興趣,他按照時間記錄下了到達海港的每一艘船只情况;對於第i艘到達的船,他記錄了這艘船到達的時間ti (單比特:秒),船上的乘客數是ki,以及每名乘客的國籍xi,1,xi,2,......,xi,kix_{i, 1}, x_{i, 2}, ......, x_{i, k_i}xi,1,xi,2,......,xi,ki。

小K統計了n艘船的信息,希望你幫忙計算出以每一艘船到達時間為止的24小時(24小時=86400秒)內所有乘船到達的乘客來自多少個不同的國家。

形式化地講,你需要計算n條信息。對於輸出的第i條信息,你需要統計滿足 ti - 86400 < tp <= ti的船只p,在所有的xp,jx_{p, j}xp,j中,總共有多少個不同的數。

輸入

第一行輸入一個正整數n,錶示小K統計了n艘船的信息。

接下來n行,每行描述一艘船的信息:前兩個整數ti和ki分別錶示這艘船到達海港的時間和船上的乘客數量,接下來ki個整數xi,jx_{i, j}xi,j錶示船上乘客的國籍。

保證輸入的ti是遞增的,單比特是秒;錶示從小K第一次上班開始計時,這艘船在第 ti 秒到達海港。

保證1≤n≤105,ki≥1,∑ki≤3×105,1≤xi,j≤105,1≤ti−1<ti≤1091 \le n \le 10^5, k_i \ge 1, \sum{k_i} \le 3 \times 10^5, 1 \le x_{i, j} \le 10^5, 1 \le t_{i - 1} \lt t_i \le 10^91≤n≤105,ki≥1,∑ki≤3×105,1≤xi,j≤105,1≤ti−1<ti≤109。

其中∑ki\sum{k_i}∑ki錶示所有的ki的和,∑ki=k1+k2+...+kn\sum{k_i} = k_1 + k_2 + ... + k_n∑ki=k1+k2+...+kn。

輸出

輸出n行,第i行輸出一個整數錶示第i艘船到達後的統計信息。

樣例輸入

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

樣例輸出

3
4
4

提示

第一艘船在第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個不同的國家。

【子任務】

  • 對於10%的測試點,n=1,∑ki≤10,1≤xi,j≤10,1≤ti≤10n = 1, \sum{k_i} \le 10, 1 \le x_{i,j} \le 10, 1 \le t_i \le 10n=1,∑ki≤10,1≤xi,j≤10,1≤ti≤10;
  • 對於20%的測試點,1≤n≤10,∑ki≤100,1≤xi,j≤100,1≤ti≤327671 \le n \le 10, \sum{k_i} \le 100, 1 \le x_{i,j} \le 100, 1 \le t_i \le 327671≤n≤10,∑ki≤100,1≤xi,j≤100,1≤ti≤32767;
  • 對於40%的測試點,1≤n≤100,∑ki≤100,1≤xi,j≤100,1≤ti≤864001 \le n \le 100, \sum{k_i} \le 100, 1 \le x_{i,j} \le 100, 1 \le t_i \le 864001≤n≤100,∑ki≤100,1≤xi,j≤100,1≤ti≤86400;
  • 對於70%的測試點,1≤n≤1000,∑ki≤3000,1≤xi,j≤1000,1≤ti≤1091 \le n \le 1000, \sum{k_i} \le 3000, 1 \le x_{i,j} \le 1000, 1 \le t_i \le 10^91≤n≤1000,∑ki≤3000,1≤xi,j≤1000,1≤ti≤109;
  • 對於100%的測試點,1≤n≤105,∑ki≤3×105,1≤xi,j≤105,1≤ti≤1091 \le n \le 10^5, \sum{k_i} \le 3 \times 10^5, 1 \le x_{i,j} \le 10^5, 1 \le t_i \le 10^91≤n≤105,∑ki≤3×105,1≤xi,j≤105,1≤ti≤109。

程序實現

#include<bits/stdc++.h>
using namespace std;
int x[100001],n,sum;
struct node
{
int t,p;
};
queue<node>h;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int t,p;
scanf("%d%d",&t,&p);
for(int j=1;j<=p;j++){
node now;
int g;
scanf("%d",&g);
now.t=t;now.p=g;
h.push(now);
x[g]++;
if(x[g]==1)
{
sum++;
}
}
node a=h.front();
node now=h.back();
while(a.t<=now.t-86400)
{
x[a.p]--;
if(x[a.p]==0)
{
sum--;
}
h.pop();
a=h.front();
}
printf("%d\n",sum);
}
}

版权声明:本文为[瘋狂的函數]所创,转载请带上原文链接,感谢。 https://gsmany.com/2022/01/202201072031027346.html