문제
로그 파일이 하나 있습니다. 이 로그 파일에는 N개의 로그가 저장되어 있습니다.
가희에게 Q개의 임무가 주어졌습니다. 가희는 각 임무마다 시작 시각, 종료 시각, 로그 레벨을 제공받습니다.
가희는 매 임무마다 주어진 시작 시각과 종료 시각 사이에, 로그 레벨이 lv 이상인 로그가 몇 번 발생하였는지 답해야 합니다.
이 때, 시작 시각과 종료 시각에 발생한 로그도 답을 계산하는 데 포함해야 합니다.
가희를 도와 임무를 수행하는 프로그램을 작성해 주세요.
입력
1번째 줄에 로그 파일에 있는 로그의 갯수 N과 쿼리의 갯수 Q가 주어집니다.
2번째 줄부터 N+1번째 줄까지, 로그 발생 시각과 LV이 #으로 구분되어 주어집니다.
N+2번째 줄부터 N+Q+1번째 줄까지 Q개의 임무가 다음 형식으로 주어집니다.
시작 시각#종료 시각#LV
시작시각, 종료 시각, 로그 발생 시각은 YYYY-MM-DD hh:mm:ss형식으로 주어집니다.
출력
임무에 대한 답을 한 줄에 하나씩 출력해 주세요.
제한
1 ≤ N ≤ 2×105
1 ≤ Q ≤ 2×105
1 ≤ LV ≤ 6
- 로그는 먼저 발생한 순으로 주어집니다.
- 같은 시각에 여러 개의 로그가 발생할 수도 있습니다.
- 로그들이 발생한 시각은 2000년 1월 1일 00:00:00 이후이며, 이 대회가 시작한 시각 이전입니다.
예제 입력 1
2 2
2021-04-05 17:17:11#1
2021-04-05 17:18:11#2
2021-04-05 17:17:11#2021-04-05 17:18:11#1
2021-04-05 17:18:11#2021-04-05 17:19:11#3
예제 출력 1
2
0
1번째 쿼리는 2021년 4월 5일 17시 17시 11분부터, 2021년 4월 5일 17시 18시 11분까지 발생한 로그 중에서, 로그 레벨이 1 이상인 것의 개수를 구하는 문제입니다.
이 사이에 발생한 로그는 2021년 4월 5일 17시 17시 11분에 발생한 레벨 1 로그와, 2021년 4월 5일 17시 18시 11분에 발생한 레벨 2 로그입니다.
2개 다 로그 레벨이 1 이상이므로 2를 출력합니다.
2번째 쿼리는 2021년 4월 5일 17시 18분 11분부터, 2021년 4월 5일 17시 19분 11분까지 발생한 로그 중에서, 로그 레벨이 3 이상인 것의 개수를 묻는 문제입니다.
로그 레벨이 3 이상 로그는 파일에 없으므로, 2번째 쿼리의 답은 0이 됩니다.
풀이
