Algorithm

Problem link- https://www.spoj.com/problems/MOVIFAN/

MOVIFAN - Movie Fan

no tags 

 

Alice is a cinephile. She wanted to watch a recently released movie. There are many movie shows whose start time and length are given. Your task is to help Alice count the number of ways she can watch the movie. Since she is a cinephile, she can watch many shows as long as they do not overlap.

Input

First line contains an integer t denoting the number of test cases.

Each test case contains n, l denoting number of shows and length of the shows.

n integer follows denoting start time of each show.

1 <= t <= 10

1 <= n, l <= 300000

Output

Print the number of ways Alice can watch shows if she wants to watch at least one show modulo 1000000007.

Example

Input:
3
3 4
3 8 12
3 1
1 2 3
3 3
3 5 9

Output:
7
7
5

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
#define MOD                 1000000007LL
#define EPS                 1e-9
#define io                  ios_base::sync_with_stdio(false);cin.tie(NULL);

const int MAXN = 3e5+5;

ll st[MAXN], dp[MAXN], cum[MAXN];

int main(){
	io;
	int t;
	cin >> t;
	while(t--){
		int n, l;
		cin >> n >> l;
		memset(dp, 0, sizeof dp);
		memset(cum, 0, sizeof cum);
		for(int i = 1;i <= n; i++)
			cin >> st[i];
		sort(st, st+n+1);
		int k = 1;
		ll ans = 0;
		for(int i = 1;i <= n; i++){
			while(k <= i && st[k] + l <= st[i])
				k++;
			dp[i] = (cum[k-1] + 1) % MOD;
			cum[i] = (cum[i-1] + dp[i]) % MOD;
			// cout << i << " " << cum[i] << " " << dp[i] << endl;
			ans = (ans + dp[i]) % MOD;
		}
		cout << ans << endl;
	}
	return 0;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
3
3 4
3 8 12
3 1
1 2 3
3 3
3 5 9

Output

x
–
+
cmd
7
7
5
Advertisements

Demonstration

SPOJ Solution-Movie Fan-Solution in C, C++, Java, Python

Previous
SPOJ Solution - Test Life, the Universe, and Everything - Solution in C, C++, Java, Python