# HackerEarth Modified LIS problem solution

In this HackerEarth Modified LIS problem, You are given a sequence of N integers as A1, A2, ... , AN. Let B be a sub-sequences of A, of maximum possible length (say k), such that each of them satisfies following conditions:

|Bi| > |Bi-1|

Bi * Bi-1 < 0

for all i = 2, 3, ... k

Find number of distinct sub-sequences of length k that satisfy above conditions. Two sub-sequences are distinct if they are made up using different set of indices of sequence A.

## HackerEarth Modified LIS problem solution.

`#include <bits/stdc++.h> using namespace std; const int N = 100001;const int M = N << 3;const int MOD = 1000000007; typedef pair<int, int> pii;typedef long long LL; #define mp make_pair#define pb push_back pii positive[M], negative[M];int A; inline void add(int &a, int b) {    a += b;    if (a >= MOD) a -= MOD;} pii best(pii &a, pii b, pii c) {    a = max(b, c);    if (b.first == c.first) a.second = (b.second + c.second) % MOD;} void update(int S, int E, int L, int R, int I, int J, int V, pii *tree) {    if (S > E || E < L || S > R) return;    if (S == E) {        int P = tree[I].first;        if (P > J) return;        else if (P == J) add(tree[I].second, V);        else {tree[I] = mp(J, V);}        return;    }    int Mid = (S + E) >> 1; int Lt = (I << 1); int Rt = Lt | 1;    update(S, Mid, L, R, Lt, J, V, tree);    update(Mid + 1, E, L, R, Rt, J, V, tree);    best(tree[I], tree[Lt], tree[Rt]);} pii read(int S, int E, int L, int R, int I, pii *tree) {    if (S > E || E < L || S > R) return mp(0, 0);    if (L <= S && E <= R) return tree[I];    int Mid = (S + E) >> 1; int Lt = (I << 1); int Rt = Lt | 1;    pii a = read(S, Mid, L, R, Lt, tree);    pii b = read(Mid + 1, E, L, R, Rt, tree);    pii res;    best(res, a, b);    return res;} void print(pii x) {    cout << x.first << " " << x.second << "\n";} int main() {    //freopen("input.in", "r", stdin);    //freopen("output.out", "w", stdout);    pii ans = mp(-1, -1), call;    int n, sign = 1;    scanf("%d", &n);    for (int i = 1; i <= n; ++i) {        scanf("%d", &A);        assert(A != 0);        sign = (A > 0);        if (!sign) A = -A;        call = read(1, N - 1, 1, A - 1, 1, sign ? negative : positive);        if (call.second == 0) ++call.second;        ++call.first;        update(1, N - 1, A, A, 1, call.first, call.second, sign ? positive : negative);    }    best(ans, positive[1], negative[1]);    printf("%d %d\n", ans.first, ans.second);    return 0;}`

### Second solution

`#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<cctype>#include<cstdlib>#include<algorithm>#include<bitset>#include<vector>#include<list>#include<deque>#include<queue>#include<map>#include<set>#include<stack>#include<cmath>#include<sstream>#include<fstream>#include<iomanip>#include<ctime>#include<complex>#include<functional>#include<climits>#include<cassert>#include<iterator>#include<unordered_map>#include<unordered_set>//#include<quadmath.h>using namespace std;namespace test{    void end_test(){        int val;        if (cin >> val){            exit(1);        }    }    void range_test(int t, int l, int r){        if (t < l || r < t){            exit(1);        }    }}#define MOD 1000000007LLstruct st{    long long int way;    long long int maxt;    st(){        way = maxt = 0;        way = 0;    }};st merge(st a, st b){    st r;        r.maxt = max(a.maxt, b.maxt);    if (r.maxt == a.maxt){        r.way += a.way;    }    if (r.maxt == b.maxt){        r.way += b.way;    }    r.way %= MOD;    return r;}class S{        vector<st> seg;    int N;    st emp;    inline st qq(int b, int l, int r, int ll, int rr){        if (ll <= l&&r <= rr){            return seg[b];        }        if (rr <= l || r <= ll){            return emp;        }        st R = merge(qq(b * 2 + 1, l, (l + r) >> 1, ll, rr), qq(b * 2 + 2, (l + r) >> 1, r, ll, rr));        return R;    }    inline void ADD(int b, int l, int r, int ll, st k){        if (l <= ll&&ll < r){            if (l + 1 == r){                seg[b] = merge(seg[b], k);                return;            }            ADD(b * 2 + 1, l, (l + r) >> 1, ll, k);            ADD(b * 2 + 2, (l + r) >> 1, r, ll, k);            seg[b] = merge(seg[b * 2 + 1], seg[b * 2 + 2]);        }    }public:    void resize(int n){        seg.assign(n * 4, emp);        N = n;    }    st sum(int l, int r){        return qq(0, 0, N, l, r + 1);    }    void add(int val, long long int way, long long int maxt){        st k;        k.way = way;        k.maxt = maxt;        ADD(0, 0, N, val, k);    }};#define MAX 100002int n;int a[MAX];S pos;S neg;int main(){    pos.resize(MAX);    neg.resize(MAX);    scanf("%d", &n);    test::range_test(n, 1, 100000);    for (int i = 0; i < n; i++){        scanf("%d", &a[i]);        test::range_test(abs(a[i]),0,1000000);    }    for (int i = 0; i < n; i++){        if (a[i] == 0){            continue;        }        if (a[i] < 0){            st k = pos.sum(0,abs(a[i])-1);            if (k.maxt == 0){                k.maxt = 1;                k.way = 1;            }            else{                k.maxt++;            }            neg.add(abs(a[i]), k.way, k.maxt);        }        else{            st k = neg.sum(0,abs(a[i]) - 1);            if (k.maxt == 0){                k.maxt = 1;                k.way = 1;            }            else{                k.maxt++;            }            pos.add(a[i], k.way, k.maxt);        }    }    st ans = merge(pos.sum(0, MAX - 1) , neg.sum(0, MAX - 1));    printf("%lld %lld\n", ans.maxt, ans.way);    return 0;}`