HackerEarth Research on Numbers problem solution

In this HackerEarth Research on Numbers problem Bob is studying in a research institute. He is currently researching on integer sequences. He has already done some research on famous fibonacci sequence. Now he is trying to investigate patterns in a general recursive sequence (Ai)

Sequence (Ai) is

Ai = Bi (for i <= k)

Ai = C1 * Ai-1 + C2 * Ai-2 +…….+ Ck*Ai-k (for i > k)

But while calculating the sequence he realizes that values are growing very fast. So to keep the values small he calculates values modulo 109+7 (1000000007) . So that each term of sequence will be less than 109+7.

While he is busy with his work, his girlfriend is disturbing him a lot. He wants to make her busy with some task. He gives her the task of sorting all the terms from Al to Ar of his sequence. She is very quick so he gives her same task Q times (of course with different l and r). Since sorting is very boring task so she asks you to complete the task.

You will be given two numbers l and r and you are expected to output all the terms from Al to Ar in non decreasing order. But to avoid such a large output, if there are more than 100 terms in the output print only first 100.

#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<fstream>
#include<cstdlib>
#include<cassert>
#include<vector>
#include<algorithm>
#include<stack>
#include<set>
#include<map>
#include<list>
#include<math.h>
#include<ctime>
#define LL long long
#define ULL unsigned long long
#define F first
#define S second
#define pb push_back
#define FOR(i,lb,ub) for(i=lb;i<=ub;i++)
#define RFOR(i,ub,lb) for(i=ub;i>=lb;i--)
#define FORS(it,v) for(it=v.begin();it!=v.end();it++)
#define st_clk double st=clock();
#define end_clk double en=clock();
#define show_time cout<<"tTIME="<<(en-st)/CLOCKS_PER_SEC<<endl;
#define sc(n) scanf("%d",&n)
#define scst(n) scanf("%s",n)
#define f_in(st) freopen(st,"r",stdin);
#define f_out(st) freopen(st,"w",stdout);
LL gcd(LL a, LL b) { return b?gcd(b,a%b):a; }
using namespace std;
 
#define MOD 1000000007
int ar[1000006];
class array
{
    public:
        int a[105],size;
    array()
    {
        //memset(a,0,sizeof(a));
        size=0;
    }
};
class node
{
    public:
        int start,end;
        node *left,*right;
        int mx[105],ind;
    node()
    {
        left = NULL;
        right = NULL;
        memset(mx,0,sizeof(mx));
        ind=0;
    }
};
node* initialise(int start,int end)
{
    int i;
    node *root = new node;
    root->start = start;
    root->end = end;
    int mid = (start+end)/2;
    if (end-start>=100)
    {
        root->left = initialise(start,mid);
        root->right = initialise(mid + 1,end);
        int temp[300],t_ind=0;
        for (i=0;i<root->left->ind;i++) temp[t_ind++] = root->left->mx[i];
        for (i=0;i<root->right->ind;i++) temp[t_ind++] = root->right->mx[i];
        sort(temp,temp+t_ind);
        if (t_ind<=100)
        {
            FOR(i,0,t_ind-1)
                root->mx[i] = temp[i];
            root->ind = t_ind;
        }
        else
        {
            FOR(i,0,99)
                root->mx[i] = temp[i];
            root->ind = 100;
        }
    }
    else
    {
        FOR(i,start,end)
            root->mx[root->ind++] = ar[i];
    }
    return root;
}
array query(node* root,int i,int j)
{
    array a;
    if (root->start>j || root->end<i)
        return a;
    if (i<=root->start && j>=root->end)
    {
        for (int indx=0;indx<root->ind;indx++)
            a.a[a.size++] = root->mx[indx];
        sort(a.a,a.a+a.size);
        return a;
    }
    else
    {
        array a1,a2;
        if (root->left)
        {
            a1 = query(root->left,i,j);
        }
        if (root->right)
        {
            a2 = query(root->right,i,j);
        }
        if (a1.size == 0 && a2.size==0)
        {
            int start_ind = max(root->start,i),end_ind = min(root->end,j);
            for (int indx = start_ind;indx<=end_ind;indx++)
                a1.a[a1.size++] = ar[indx];
            sort(a1.a,a1.a+a1.size);
            return a1;
        }
        
            if (a1.size == 0)
                return a2;
            if (a2.size == 0)
                return a1;
            int temp[300],t_ind=0;
            for (int indx=0;indx<a1.size;indx++)
                temp[t_ind++] = a1.a[indx];
            for (int indx=0;indx<a2.size;indx++)
                temp[t_ind++] = a2.a[indx];
            sort(temp, temp+t_ind);
            array final;
            int limit = min(100,a1.size+a2.size);
            for (int indx=0;indx<limit;indx++)
                final.a[indx] = temp[indx];
            final.size = limit;
        return final;
    }
}
int main()
{
     #ifndef ONLINE_JUDGE
     //f_in("simple_in.txt");
     //f_out("simple_out.txt");
     #endif
     st_clk
     int t,i,j;
     cin>>t;
     while (t--)
     {
        LL k,q,c[6];
        cin>>q>>k;
        FOR(i,1,k)
            cin>>ar[i];
        FOR(i,1,k)
            cin>>c[i];
        FOR(i,k+1,1000001)
        {
            ar[i] = (c[1]*ar[i-1])%MOD;
            FOR(j,2,k)
                ar[i] = (ar[i] + c[j]*ar[i-j])%MOD;
        }
        node *root = initialise(1,1000001);
        while (q--)
        {
            int l,r;
            scanf("%d %d",&l,&r);
            array rr = query(root,l,r);
            for (i=0;i<rr.size-1;i++)
                printf("%d ",rr.a[i]);
            printf("%dn",rr.a[i]);
        }
        end_clk
        //show_time
     }
return 0;
}