洛谷笔记 - P2058 [NOIP2016 普及组] 海港

发表于 更新于 本文字数： 1k 阅读时长 ≈ 4 分钟

栈真好用。

题目背景

NOIP2016 普及组 T3

题目描述

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

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

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

形式化地讲，你需要计算 nn 条信息。对于输出的第 ii 条信息，你需要统计满足 ti−86400<tp≤tit_i-86400<t_p \le t_i 的船只 pp，在所有的 xp,jx_{p,j} 中，总共有多少个不同的数。

输入格式

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

接下来 nn 行，每行描述一艘船的信息：前两个整数 tit_i和 kik_i分别表示这艘船到达海港的时间和船上的乘客数量，接下来 kik_i个整数 xi,jx_{i,j}表示船上乘客的国籍。

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

保证 1≤n≤1051 \le n \le 10^5， ，1≤xi,j≤1051\le x_{i,j} \le 10^5， 1≤ti−1≤ti≤1091 \le t_{i-1}\le t_i \le 10^9。

其中∑ki\sum{k_i}表示所有的 kik_i的和。

输出格式

输出 nn 行，第 ii 行输出一个整数表示第 ii 艘船到达后的统计信息。

输入输出样例

样例输入 1

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

样例输出 1

1
2
3
3
4
4

样例输入 2

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

样例输出 2

1
2
3
4
3
3
3
4

说明 / 提示

【样例解释 1】

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

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

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

【样例解释 2】

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

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

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

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

【数据范围】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
#include<stack>
using namespace std;
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int k;
        cin>>k;
        int a[100001],b[100001];
        stack<int> ii;
        for(int p=1;p<=k;p++){
            cin>>a[p];
        }
        for(int p=1;p<=k;p++){
            cin>>b[p];
        }
        int l=1;
        for(int p=1;p<=k;p++){
            ii.push(a[p]);
            while(ii.top()==b[l]){
                ii.pop();
                l++;
                if(ii.empty()){
                    break;
                }
            }
        }
        if(ii.empty()){
            cout<<"Yes"<<endl;
        }else cout<<"No"<<endl;
    }
    return 0;
}