Codeforces Round #793 (Div. 2)(C. LIS or Reverse LIS?)

just make the array like that ->->->

(low-> -> high -> -> low)

So we can divide it by two part (low -> -> high)[fot LIS] & (high -> -> low)[reverse LIS]

Example:1 1 2 3 4 3 2 2 1

LIS= 1 1 2 3 4 3 2 2 1

Reverse LIS=1 1 2 3 4 3 2 2 1

Example:1 1 2 2 1

LIS=1 1 2 2 1

Reverse LIS=1 1 2 2 1

Example:1 7 9 6 5

LIS= 1 7 9 6 5

Reverse LIS= 1 7 9 6 5

///Bismillahir Rahmanir Rahim

///Author: Tanvir Ahmmad

///CSE,Islamic University,Bangladesh

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<string>

#include<cstring>

#include<sstream>

#include<cmath>

#include<cstring>

#include<vector>

#include<queue>

#include<map>

#include<set>

#include<stack>

#include<vector>

#include<iterator>

#include <functional> ///sort(arr,arr+n,greater<int>()) for decrement of array

/*every external angle sum=360 degree

  angle find using polygon hand(n) ((n-2)*180)/n*/

///Floor[Log(b)  N] + 1 = the number of digits when any number is represented in base b

using namespace std;

typedef long long ll;

int main()

{

    ll n,tst,num;

    cin>>tst;

    while(tst--)

    {

        cin>>n;

        ll one=0,more=0;

        map<ll,ll>mp;

         map<ll,ll>::iterator it;

        for(ll i=0; i<n; i++)

        {

            cin>>num;

            if(mp.find(num)==mp.end())

                mp[num]=1;

            else

                mp[num]++;

        }

        for(it=mp.begin();it!=mp.end();it++)

        {

             if(it->second>=2) more++;

              if(it->second==1) one++;

        }

        if(one>=1) more+=ceil(double(one)/2.0);

        cout<<more<<endl;

    }

    return 0;

}

///Alhamdulillah

 

Problem Link:https:https://codeforces.com/contest/1682/problem/C