# PROBLEM LINK:

Practice

Contest

**Author:** ravikiran0606

**Editorialist:** ravikiran0606

# DIFFICULTY:

MEDIUM

# PREREQUISITES:

DP,MATH,BINARY SEARCH

# PROBLEM:

In this problem, we have N + 1 bus stops in a straight line. All of them are numbered with integers from 0 to N in the order in which they follow from RK's college. There are M buses running between the college and the beach: the i-th bus goes from stop s_{i} to t_{i} (s_{i} < t_{i}), visiting all the intermediate stops in the order in which they follow on the segment. RK can get on the i-th bus on any stop numbered from s_{i} to t_{i} - 1 inclusive, but he can get off the i-th bus only on the bus stop t_{i}. We need to find the number of ways RK can go from college to beach.

# EXPLANATION:

In this question, for every stop from 0 to N lets calculate k_{x} - number of ways come to them. Consider the i-th bus, number of ways come to stop t_{i} supplied i-th bus is equal to number of ways to embus to i-th bus. One can embus to i-th bus on the stops s_{i}, s_{i} + 1, ..., t_{i} - 1. Thus number of ways come to stop t_{i} in the i bus is equal to sum k_{si} + k_{si} + 1 + ... + k_{ti} - 1. Finally, lets note that overall number of ways to come to stop t_{i} is the sum of numbers of ways to come to stop t_{i} on every bus.

It's remained two problems.

First problem: 0 ≤ n ≤ 10^{9}. Therefore all k_{x} not climb in memory limit. But we need to know only non-zero k_{x}. For instance, one can gripe coordinates: create list of all occured stops (and also stops 0 and n), sort this list, delete the repeated stops and replace all numbers of stops they indexes in this list. After this operations all number of stops not exceed 200001, and all k_{x} are climb to the memory.

Second problem: If we will use loop "for" for counting sum k_{si} + k_{si} + 1 + ... + k_{ti} - 1, asymptotic of time of working will be O(m^2). There is an easy way to solve this problem: one can create and update array sum[], such that sum[i] = k[0] + k[1] + ... + k[i - 1], by another words, sum[0] = 0, sum[i + 1] = sum[i] + k[i].
Then number of ways to come to stop t_{i} using bus i is equal to sum[t_{i}] - sum[s_{i}].
So time complexity is **O(m logm)** , memory complexity is **O(m)**.

# AUTHOR'S SOLUTION:

Author's solution can be found here

asked
**14 Mar, 00:07**

4★ravikiran0606

4●1

accept rate:
0%