13922번 - Suspicious Samples 다국어

Fatima is a researcher. She currently studies water circulation in her country river basins. She collects data samples from various meteorological stations that measure diverse climate-related values. Fatima then searches for interesting patterns in those samples. She uses a program which reads incoming samples’ data in real time and outputs those samples which are interesting or suspicious in some way. The decision whether a sample is “interesting” or “suspicious” is based on a fixed set of conditions, such as “the value is greater than the average of the last two hours” or “the value is lower than anything else in the last five minutes” which are easy to program into a computer.

Today, Fatima is in doubt about her yesterday’s results and she came to see you, an experienced programmer. She thinks that her program did not evaluate the data correctly and she asks you to help her verify its results. In particular, she brings the complete sequence of samples and describes the set of conditions to you. Your program has to read the samples and produce the output according to the conditions. Fatima will then compare the output of your program to the output of her program and decide what has to be done next.

There are more test cases. The first line of each test case contains one integer N (1 ≤ N ≤ 10⁵ ), giving the number of samples. Then there are N lines, each describing one sample. The line contains two integers T_i and V_i (1 ≤ T_i ≤ 10⁹ , 1 ≤ V_i ≤ 10⁴ ), meaning that the sample value V_i was acquired in time T_i . The times are given in seconds elapsed since some fixed moment in the past and they form a strictly increasing sequence (∀i, k 1 ≤ i < k ≤ N : T_i < T_k).

The next line of the input contains one integer C (1 ≤ C ≤ 10), the number of conditions to evaluate. Each of the following C lines specifies one condition C_j . The line contains three tokens separated with a space:

• A relation operator R_j , which is either “gt” (greater than) or “lt” (less than).
• An aggregate function F_j , one of the “min” (minimum), “max” (maximum), or “avg” (average).
• An integer number L_j specifying the length of the time interval to be concerned, in seconds.

In general, a condition applied to a sample value V_i checks how V_i is related to some aggregate feature of the samples which were acquired before V_i . The function F_j specifies exactly that feature.

To be more specific, let S_ij be the set of all samples which were acquired before V_i but no more than L_j seconds earlier. The sample value V_i satisfies the condition C_j if and only if the relation V_iR_jF_j (S_ij ) holds. For example, the sample value 800 in conjunction with “lt min 300” can be read as “is 800 less than the minimum sample value acquired in the previous 5 minutes before this 800 was obtained?”. Note that sample V_i is not an element of S_ij

For each condition, print one integer: the number of samples whose values satisfy that particular condition. If there are no samples in the time interval specified by the condition, the condition is never considered satisfied.