시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
6 초 | 512 MB | 137 | 43 | 18 | 19.780% |
There are N towns along a deep linear valley in JOI Country. Towns are numbered 0, 1, . . . , N −1 in order of distance from the sea.
Mr. I, the chair of JOI Country Scientific Committee, is going to maintain bidirectional communication cables between the towns. Currently there are no cables in JOI Country.
Mr. I has a cable construction plan for C days. The plan on the (i + 1)-th day (0 ≤ i ≤ C − 1) is represented by three integers Ti, Xi, Yi, which mean:
Cliff collapse often happens in JOI Country. If collapse happens between town x and town x + 1 (0 ≤ x ≤ N − 2), any cable which connects a town numbered at most x and a town numbered at least x + 1 becomes unavailable. In JOI Country, when collapse happens, they choose some towns to install base stations. Base stations should be installed in such a way that, from any town, it is possible to reach a base station by following available cables.
Mr. I is concerned with the number of towns to install base stations when collapse happens during the construction period. He has Q questions: the (j + 1)-th question is represented by two integers Wj, Pj, which mean that he wants to know the minimum number of base stations which should be installed if collapse happens between town Pj and town Pj + 1 at the end of the (Wj + 1)-th day.
You, as an assistant of Mr. I, are in charge of writing a program to answer Mr. I’s questions.
5 8 2 0 0 1 0 1 3 0 2 4 0 4 0 1 1 3 0 0 3 0 1 2 0 4 3 3 1 7 3
3 2
Consider the case where there are 5 towns. In the following, (x, y) denotes a cable connecting town x and town y.