Trip

Description:

You are starting out on a long (really long) trip. On the way, there are N gas stations, the locations of which are given as a1,a2,…,aN. Initially you are located at the gas station at a1, and your destination is at location a_N. Your car can only store enough fuel to travel atmost M units without refilling. You can stop at any station and refill the car by any amount. Now you wish to plan your trip such that the number of intermediate stops needed to reach the destination is minimum, and also how many ways are there to plan your trip accordingly. Input : The first line two space seperated integers N and M. N lines follow, and the ith line has the value ai (0 <= ai <= 1000000000). The input will be such that a solution will always exist. Output : Output two space seperated integers : The least number of stops, and the number of ways to plan the trip which uses the least number of stops. Output this value modulo 1000000007. Sample Input : 6 3 0 1 3 4 7 10 Sample Output : 3 2 Constraints : 2 <= N <= 1000000 1 <= M <= 1000 a_1 < a_2 < .. < a_N

Program :

#include<stdio.h>
#include<stdlib.h>
#define MOD 1000000007
#define BUF 4096
    int arr[1000000];
    int temp1[1000000];
    int temp2[1000000];
    char ibuf[BUF];
    int ipt = BUF;
    int readInt()
    {
    while (ipt < BUF && ibuf[ipt] < '0')
    ipt++;
    if (ipt == BUF)
    {
    fread(ibuf, 1, BUF, stdin);
    ipt = 0;
    while (ipt < BUF && ibuf[ipt] < '0')
    ipt++;
    }
    int n = 0;
    while (ipt < BUF && ibuf[ipt] >= '0')
    n = (n*10)+(ibuf[ipt++]-'0');
    if (ipt == BUF)
    {
    fread(ibuf, 1, BUF, stdin);
    ipt = 0;
    while (ipt < BUF && ibuf[ipt] >= '0')
    n = (n*10)+(ibuf[ipt++]-'0');
    }
    return n;
    }
    int main()
    {
    int m,n,i,j,min,k;
    long long count=0;
    n=readInt();
    m=readInt();
    for(i=0;i<n;i++)
    arr[i]=readInt();
    temp2[0]=1;
    j=k=count=0;
    for(i=1;i<n;i++)
    {
    while(arr[i]-arr[j] > m)
    count-=temp2[j++];
    temp1[i]=temp1[j]+1;
    while(temp1[k]==temp1[j])
    count+=temp2[k++];
    temp2[i]=count%MOD;
    }
    printf("%d %d\n",temp1[n-1]-1,temp2[n-1]);
    return 0;
    }