HackerEarth Girls and the Boxes problem solution

by
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

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("%dn" ,*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
#endif

typedef 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;
}