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


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 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 %lld\n", ans.maxt, ans.way);
return 0;
}