# HackerEarth Girls and the Boxes problem solution

In this HackerEarth Girls and the Boxes problem solution You are given n boxes and each box contains two small boxes of Red and Blue color. The size of the Red and Blue colored boxes are bi and ri respectively.

Consider a sequence of distinct integers x1, x2, ..., xk(1 <=xi <=n).

Consider x  to be a suitable sequence if, for every 1<=i<k holds bxi < rxi+1 and rxi < bxi+1.

Determine the maximum possible size of the suitable sequence.

## HackerEarth Girls and the Boxes problem solution.

`#include<bits/stdc++.h>using namespace std;#define ll long long#define pb push_back#define lb(a) ((a)&(-(a)))const int maxn = 1e6 + 20;int r[maxn] , b[maxn] , dp[maxn];vector<int> pnt[maxn];int fen[2][maxn];void update(int p , int val , int id){    for(p += 5; p < maxn; p += lb(p))        fen[id][p] = max(fen[id][p] , val);}int get(int p , int id){    int res = 0;    for(p += 5; p > 0; p -= lb(p))        res = max(res , fen[id][p]);    return res;}int main(){       int n;    scanf("%d", &n);    n *= 2;    vector<int> cmp;    for(int i = 0; i < n; i += 2)    {        scanf("%d%d", &r[i], &b[i]);        cmp.pb(r[i]);        cmp.pb(b[i]);        r[i + 1] = b[i] , b[i + 1] = r[i];    }    sort(cmp.begin() , cmp.end());    cmp.resize(unique(cmp.begin() , cmp.end()) - cmp.begin());    for(int i = 0; i < n; i++)    {        r[i] = lower_bound(cmp.begin() , cmp.end() , r[i]) - cmp.begin();        b[i] = lower_bound(cmp.begin() , cmp.end() , b[i]) - cmp.begin();        pnt[r[i]].pb(i);    }    for(int i = 0; i < (int)cmp.size(); i++)    {        for(auto ind : pnt[i])            dp[ind] = get(b[ind] - 1 , !(ind & 1)) + 1;        for(auto ind : pnt[i])            update(b[ind] , dp[ind] , ind & 1);    }    printf("%d\n" ,*max_element(dp , dp + n));}`

### Second solution

`#ifndef BZ#pragma GCC optimize "-O3"#endif#include <bits/stdc++.h>#define FASTIO#define ALL(v) (v).begin(), (v).end()#define rep(i, l, r) for (int i = (l); i < (r); ++i)#ifdef FASTIO#define scanf abacaba#define printf abacaba#endiftypedef long long ll;typedef long double ld;typedef unsigned long long ull;using namespace std;template<typename T> T mo(T x, T y) { x %= y; return x <= 0 ? x + y : x; }const int MX = 1000 * 1000 + 7;struct T {    int t[4 * MX];    void c(int v, int tl, int tr, int pos, int val) {        t[v] = max(t[v], val);        if (tl != tr) {            int tm = (tl + tr) >> 1;            if (pos <= tm) {                c(v + v, tl, tm, pos, val);            } else {                c(v + v + 1, tm + 1, tr, pos, val);            }        }    }    int gt(int v, int tl, int tr, int l, int r) {        if (r < tl || l > tr) {            return 0;        }        if (tl >= l && tr <= r) {            return t[v];        }        int tm = (tl + tr) >> 1;        return max(gt(v + v, tl, tm, l, r), gt(v + v + 1, tm + 1, tr, l, r));    }};T t[2];int main() {#ifdef FASTIO    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);#endif    int n;    cin >> n;    vector<tuple<int, int, int> > pts;    vector<int> xx;    for (int i = 0; i < n; i++) {        int x, y;        cin >> x >> y;        pts.emplace_back(x, y, 0);        pts.emplace_back(y, x, 1);        xx.push_back(x);        xx.push_back(y);    }    sort(xx.begin(), xx.end());    xx.resize(unique(xx.begin(), xx.end()) - xx.begin());    auto fn = [&](int x) -> int {        return lower_bound(xx.begin(), xx.end(), x) - xx.begin() + 1;    };    for (auto& v : pts) {        get<0>(v) = fn(get<0>(v));        get<1>(v) = fn(get<1>(v));    }    sort(pts.begin(), pts.end(), [&](auto a, auto b) {        if (get<0>(a) == get<0>(b)) {            return get<1>(a) > get<1>(b);        }        return get<0>(a) < get<0>(b);    });    int ans = 0;    for (auto v : pts) {        int cans = t[get<2>(v) ^ 1].gt(1, 1, 2 * n, 1, get<1>(v) - 1) + 1;        ans = max(ans, cans);        t[get<2>(v)].c(1, 1, 2 * n, get<1>(v), cans);    }    cout << ans << "\n";    return 0;}`