HackerEarth Select the subset problem solution

In this HackerEarth Select the subset problem solution You are given an array A and B of size N.

You must select a subset of indices from 1 to N such that for any pair of indices (x,y), x != y in the subset one of the following conditions holds true:

1. A[x] < A[y] and B[x] < B[y]
2. A[x] > A[y] and B[x] > B[y]
3. A[x] = A[y] and B[x] != B[y]

Your task is to determine the largest possible size of a subset that satisfies the provided conditions.

HackerEarth Select the subset problem solution.

#include "bits/stdc++.h"
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#define time__(d) \
    for ( \
        auto blockTime = make_pair(chrono::high_resolution_clock::now(), true); \
        blockTime.second; \
        debug("%s: %d ms\n", d, (int)chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - blockTime.first).count()), blockTime.second = false \
    )
#ifdef LOCAL
#include "pprint.hpp"
#endif
#define endl '\n';
#define pb push_back
#define mod 1000000007
#define ll long long int
#define prn(x) cerr<<x<<endl;
#define all(x) x.begin(),x.end()
using namespace std;
#define test_case 1

int lis(vector<int> &v){
    int l=1;
    vector<int> Lis;
    Lis.pb(v[0]);
    for(int i=1;i<(int)v.size();++i){
        if(v[i]>Lis[l-1]){
            Lis.pb(v[i]);
            ++l;
        }
        else{
            int pos = lower_bound(all(Lis),v[i])-Lis.begin();
            Lis[pos]=v[i];
        }
    }
    return l;
}

void solution(){
    int n;
    cin>>n;
    assert(n>=1 && n<=100000);
    vector<int> a(n+1),b(n+1);
    for(int i=1;i<=n;++i){
        cin>>a[i];
        assert(a[i]>=1 && a[i]<=1000000000);
    }
    for(int i=1;i<=n;++i){
        cin>>b[i];
        assert(b[i]>=1 && b[i]<=1000000000);
    }
    vector<pair<int,int>> v;
    for(int i=1;i<=n;++i){
        v.pb({a[i],b[i]});
    }
    sort(all(v));
    vector<int> vv;
    for(auto x:v)
        vv.pb(x.second);
    cout<<lis(vv)<<endl;
}

int main(int argc, char *argv[])
{
    int t=1;
    if(test_case)
        cin>>t;
    assert(1 <= t and t <= 10);
        while(t--){
            solution();
        }
    return 0;
}

Second solution

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int MAX_N = 1e5 + 14;

template<class cmp>
struct LS {
    vector<int> v;
    vector<pair<int, int> > his;

    void add(int x) {
        int p = upper_bound(v.begin(), v.end(), x - 1, cmp()) - v.begin();
        if (p == v.size()) {
            his.push_back({-1, 0});
            v.push_back(x);
        }
        else {
            his.push_back({p, v[p]});
            v[p] = x;
        }
    }

    void swap(LS<cmp> &od) { od.v.swap(v); }

    void merge(LS<cmp> &od) {
        if (od.v.size() > v.size())
            v.swap(od.v);
        for (int i = 0; i < od.v.size(); i++)
            if (cmp()(od.v[i], v[i])) v[i] = od.v[i];
    }

    void undo() {
        assert(his.size());
        if (his.back().first == -1)
            v.pop_back();
        else
            v[his.back().first] = his.back().second;
        his.pop_back();
    }
};

typedef LS<less<int> > Lis;
typedef LS<greater<int> > Lds;

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        pair<int, int> a[n];
        for (int i = 0; i < n; ++i)
            cin >> a[i].first;
        for (int i = 0; i < n; ++i)
            cin >> a[i].second;
        sort(a, a + n);
        Lis lis;
        for (int i = 0; i < n; ++i)
            lis.add(a[i].second);
        cout << lis.v.size() << '\n';
    }
}