HackerEarth B-Sequence problem solution

In this HackerEarth B-Sequence problem solution Any sequence A of size n is called B-sequence if:

1. A1 < A2 < ... Ak > Ak+1 > Ak+2 > ... > An where 1 <= k <= n. That is, a sequence which is initially strictly increasing and then strictly decreasing (the decreasing part may or may not be there).
2. All elements in A except the maximum element come almost twice (once in increasing part and once in decreasing part) and the maximum element comes exactly once.
3. All elements coming in decreasing part of the sequence should have come once in the increasing part of the sequence.

You are given a B-sequence S and Q operations. For each operation, you are given a value val. You have to insert val in S if and only if after insertion, S still remains a B-sequence.

After each operation, print the size of S. After all the operations, print the sequence S.

HackerEarth B-Sequence problem solution.

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,a[100005];
    cin>>n;
    int maxx=-1;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        maxx=max(maxx,a[i]);
    }
    set<int>s1,s2;
    s1.insert(a[1]);s2.insert(a[n]);
    for(int i=2;i<=n;i++)
        if(a[i]>a[i-1])s1.insert(a[i]);
    for(int i=n-1;i>=1;i--)
        if(a[i]>a[i+1])s2.insert(a[i]);
    s2.erase(s2.find(maxx));
    int q,cnt=0;    
    cin>>q;
    for(int i=1;i<=q;i++)
    {
        int val;
        cin>>val;
        if(maxx<=val)
        {
            maxx=val;
            s1.insert(val);
        }
        else
        {
            if(s1.find(val)==s1.end())s1.insert(val);
            else s2.insert(val);
        }
        int ans=s1.size()+s2.size();
        cout<<ans<<"\n";
        cnt++;
    }
    set<int> :: iterator it;
    for(it=s1.begin();it!=s1.end();it++)cout<<(*it)<<" ";
    set<int> :: reverse_iterator rit;
    for(rit=s2.rbegin();rit!=s2.rend();rit++)cout<<(*rit)<<" ";
    return 0;
}

Second solution

#include<bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pb push_back
#define si(x) scanf("%d",&x)
#define pi(x) printf("%d\n",x)
#define s(x) scanf("%lld",&x)
#define p(x) printf("%lld\n",x)
#define sc(x) scanf("%s",x)
#define pc(x) printf("%s",x)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define F first
#define S second
#define inf 4e18
#define prec(x) fixed<<setprecision(15)<<x
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define mem(x,y) memset(x,y,sizeof(x))
#define PQG priority_queue< int,std::vector<int>,std::greater<int> >
#define PQL priority_queue< int,std::vector<int>,std::less<int> >
#define PQPL priority_queue<pii ,vector< pii >, less< pii > >
#define PQPG priority_queue<pii ,vector< pii >, greater< pii > >
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)

using namespace std;

const int N=1e5+7;
int a[N];
set<int>::iterator it;
set<int>::reverse_iterator rit;

int main() {
    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);    
    #endif
    fast_io;
    int n;
    cin>>n;
    assert(n>=1 && n<=100000);
    set<int>incr;
    set<int>decr;
    int mxval=-0;
    int idx;
    for(int i=0;i<n;i++) {
        cin>>a[i];
        assert(a[i]>=1 && a[i]<=1000000000);
        if(a[i]>mxval) {
            mxval=a[i];
            idx=i;
        }
    }
    for(int i=0;i<n;i++) {
        if(i<idx) incr.insert(a[i]);
        if(i>idx) decr.insert(a[i]);
    }
    assert(n==incr.size()+decr.size()+1);
    int flag1=0,flag2=0;
    for(int i=0;i<idx;i++) {
        assert(a[i]<a[i+1]);
    }
    for(int i=idx;i<n-1;i++) {
        assert(a[i]>a[i+1]);
    }

    int q;
    cin>>q;
    assert(q>=1 && q<=100000);
    while(q--) {
        int x; cin>>x;
        assert(x>=1 && x<=1000000000);
        if(x>mxval) {
            incr.insert(mxval);
            mxval=x;
        }
        else if(x<mxval) {
            if(incr.find(x)==incr.end()) {
                incr.insert(x);
            }
            else decr.insert(x);
        }
        cout<<incr.size()+decr.size()+1<<endl;
    }
    for(it=incr.begin();it!=incr.end();it++) cout<<(*it)<<" ";
    cout<<mxval<<" ";
    for(rit=decr.rbegin();rit!=decr.rend();rit++) cout<<(*rit)<<" ";
    cout<<endl;
    
    return 0;
}