1 #include <cstdio>
2 #include <cstring>
3 #include <iostream>
4 #include <algorithm>
5 #include <map>
6 using namespace std;
7 const int maxn = 200005;
8 typedef long long ll;
9 struct car1 {
10 char number[10],state[10];
11 int length;
12 }c1[10005],c2[10005];
13
14 bool cmp1(car1 p,car1 q) {
15 if(strcmp(p.number,q.number) != 0) return strcmp(p.number,q.number) < 0;
16 else if(p.length != q.length) return p.length < q.length;
17 return strcmp(p.state,q.state) < 0;
18 }
19 bool cmp2(car1 p,car1 q) {
20 return p.length < q.length;
21 }
22 int query[90005];//存储查询时间
23 map<string,int>mp;
24 int main() {
25 int n,mm;
26 int k = 0;//有效记录数
27 int h,m,s;
28 int maxtime = 0;//停留的最长时间
29 scanf("%d%d",&n,&mm);
30 for(int i = 0; i < n; i++) {
31 scanf("%s %d:%d:%d %s",c1[i].number,&h,&m,&s,c1[i].state);
32 c1[i].length = h*3600 + m*60 + s;//换算成秒 容易比较
33 }
34 for(int i = 0; i < mm; i++) {
35 scanf("%d:%d:%d",&h,&m,&s);//将查询时间也换成秒
36 query[i] = h*3600 + m*60 +s;
37 }
38 sort(c1,c1+n,cmp1);
39 for(int i = 0; i < n-1; i++) {
40 if(strcmp(c1[i].number,c1[i+1].number) == 0 && strcmp(c1[i].state,"in") == 0 && strcmp(c1[i+1].state,"out") == 0) {//如果匹配
41 strcpy(c2[k].number,c1[i].number);
42 c2[k].length = c1[i].length;
43 strcpy(c2[k++].state,c1[i].state);
44 strcpy(c2[k].number,c1[i+1].number);
45 c2[k].length = c1[i+1].length;
46 strcpy(c2[k++].state,c1[i+1].state);
47 mp[c1[i].number] += c1[i+1].length - c1[i].length;
48 maxtime = max(maxtime,mp[c1[i].number]);//找到在停车场最长的停车时间
49 }
50 }
51 sort(c2,c2+k,cmp2);//将有效记录的车的时间按从小到大排序
52 int now = 0;
53 int car = 0;
54 //复杂度变成了O(n+m) ！！！
55 //已知查询时间是从小到大的
56 for(int i = 0; i < mm; i++) {//关键 用now存储不大于该查询时间的车辆的时间
57 while(c2[now].length <= query[i]&& now < k) {//k是有效记录数 now一定要小于k 否则段错误！！
58 if(string(c2[now].state) == "in") car++; //如果车辆的状态是in 则停车场中车数++
59 else car--;//否则车数--
60 now++;//判断下一辆车
61 }
62 printf("%d
",car);
63 }
64 map<string,int>::iterator it;
65 for(it = mp.begin(); it != mp.end(); it++) {
66 if(it->second == maxtime) printf("%s ",it->first.c_str());
67 }
68 h = maxtime / 3600;
69 m = maxtime % 3600 /60;
70 s = maxtime % 3600 % 60;
71 printf("%02d:%02d:%02d",h,m,s);
72 return 0;
73 }
