시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 222 65 37 33.036%

문제

로그 파일이 하나 있습니다. 이 로그 파일에는 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이 됩니다.

노트

2000년부터 2020년까지 연도 중에, 윤년인 것은 2000, 2004, 2008, 2012, 2016, 2020년 입니다.

출처

Contest > 가희와 함께 하는 코딩 테스트 > 가희와 함께 하는 1회 코딩 테스트 4번