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 %dn", 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 1000000007LL
struct 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 100002
int 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 %lldn", ans.maxt, ans.way);
    return 0;
}

coding problems