Gahui and Log Files
Time limit2sMemory limit512 MB
Given timestamped logs and queries with a time range and a minimum level, count how many logs in the range have level at least the threshold.
- Level
Medium5 of 10
- Topics
- Binary search, Prefix sum, Sorting, Implementation
- Solved
- No attempts yet
Problem
There is one log file. This log file stores N logs.
Gahui is given Q tasks. For each task, she is given a start time, an end time, and a log level.
For every task, Gahui must answer how many times a log with log level at least lv occurred between the given start time and end time.
Logs that occurred exactly at the start time or the end time are included in the count.
Write a program that helps Gahui carry out the tasks.
Input
The first line gives the number of logs in the log file N and the number of queries Q.
Lines 2 through N+1 give a log's occurrence time and its LV, separated by #.
Lines N+2 through N+Q+1 give the Q tasks in the following format.
start time#end time#LV
The start time, the end time, and the log occurrence time are given in the format YYYY-MM-DD hh:mm:ss.
Output
Print the answer to each task, one per line.
Constraints
- 1 ≤ N ≤ 2×10^5
- 1 ≤ Q ≤ 2×10^5
- 1 ≤ LV ≤ 6
- The logs are given in the order they occurred.
- Multiple logs may occur at the same time.
- The times at which the logs occurred are after 2000-01-01 00:00:00 and before the time this contest started.
Hint
Among the years from 2000 to 2020, the leap years are 2000, 2004, 2008, 2012, 2016, and 2020.