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("%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
#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;
}