HackerEarth Girls and the Boxes problem solution YASH PAL, 31 July 2024 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("%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#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;} coding problems