NOIP 普及组 2016 海港

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define pb push_back
 4 #define lowbit(x) (x&(-x))
 5 #define mem(a,b) memset(a,b,sizeof a)
 6 const int maxn=1e5+50;
 7 
 8 int n;
 9 int arrive[maxn];
10 int affect[maxn];
11 vector<int >ship[maxn];
12 int diff[maxn];
13 void Solve()
14 {
15     mem(affect,0);
16     mem(diff,0);
17     for(int i=1;i <= n;++i)
18     {
19         int t=lower_bound(arrive+i,arrive+n+1,arrive[i]+86400)-arrive;
20         //printf("i=%d,t=%d\n",i,t);
21         for(int j=0;j < ship[i].size();++j)
22         {
23             int native=ship[i][j];
24             if(affect[native] < i)
25                 affect[native]=i;
26             diff[affect[native]]++;
27             diff[t]--;
28             affect[native]=t;
29         }
30     }
31     for(int i=1;i <= n;++i)
32     {
33         diff[i] += diff[i-1];
34         printf("%d\n",diff[i]);
35     }
36 }
37 int main()
38 {
39     scanf("%d",&n);
40     for(int i=1;i <= n;++i)
41     {
42         int t,k;
43         scanf("%d%d",&t,&k);
44         arrive[i]=t;
45         for(int j=1;j <= k;++j)
46         {
47             int native;
48             scanf("%d",&native);
49             ship[i].pb(native);
50         }
51         sort(ship[i].begin(),ship[i].end());
52         ship[i].erase(unique(ship[i].begin(),ship[i].end()),ship[i].end());
53     }
54     Solve();
55 }
56 /**
57 5
58 1 4 4 1 2 2
59 2 2 2 3
60 10 1 3
61 100000 5 1 2 3 4 5
62 100001 5 1 2 3 4 6
63 **/