1082E - Increasing Frequency - CodeForces Solution

/*
________                               _____.___.           .___            
\______ \   ____   ____ ______  __ __  \__  |   |____     __| _/____ ___  __
 |    |  \_/ __ \_/ __ \\____ \|  |  \  /   |   \__  \   / __ |\__  \\  \/ /
 |    `   \  ___/\  ___/|  |_> >  |  /  \____   |/ __ \_/ /_/ | / __ \\   / 
/_______  /\___  >\___  >   __/|____/   / ______(____  /\____ |(____  /\_/  
        \/     \/     \/|__|            \/           \/      \/     \/      
*/


#include<bits/stdc++.h>
#include<istream>
#include<fstream>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace chrono;
using namespace __gnu_pbds;

// Macros definition
#define ll long long
#define lld long double
#define inf 1e18

template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update> ;
template<class key, class value, class cmp = std::less<key>> using ordered_map = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;
// x.find_by_order(1) -> return pointer to element present at index 1
// x.order_of_key(2) -> return index of element 2

#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
#else
#define debug(x)
#endif

template<class T> void _print(T &x) {cerr << x;}

template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}

//To make unordered_map unhackable 
// use it as unordered_map<int,int,custom_hash> mapp;
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        /* http://xorshift.di.unimi.it/splitmix64.c */
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
 
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

// Predefined values
const ll mod = 1e9+7;

void solve(){
    ll n,c;
    cin>>n>>c;
    vector<ll>a(n);
    for(int i=0; i<n; i++){
        cin>>a[i];
    }
    vector<ll>cntC(n+1);
    for(int i=0; i<n; i++){
        cntC[i+1] = cntC[i]+(a[i]==c);
    }

    ll mx = *max_element(a.begin(), a.end())+1;
    vector<vector<ll>>segs(mx);

    auto cntSegs = [&](ll l, ll r){
        return cntC[r]-cntC[l];
    };

    vector<ll>last(mx,-1);
    for(int i=0; i<n; i++){
        segs[a[i]].push_back(-cntSegs(last[a[i]]+1, i));
        last[a[i]]=i;
        segs[a[i]].push_back(1);
    }
    debug(segs);

    for(int i=0; i<mx; i++){
        segs[i].push_back(-cntSegs(last[i]+1, n));
    }

    auto calc = [&](vector<ll>&a){
        ll res=INT_MIN;
        ll bal=0;
        for(auto it : a){
            // res=max(res, bal+it);
            bal = max(0ll, bal+it);
            res=max(res, bal);
            // bal += it;/
        }
        return res;
    };

    ll ans = 0;
    for(int i=0; i<mx; i++){
        if(i==c) continue;
        ans=max(ans, calc(segs[i]));
    }

    cout<<cntSegs(0, n)+ans<<endl;
}

int main(){
	
	// Deepu Yadav
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    #ifndef ONLINE_JUDGE
	// freopen("Error.txt", "w", stderr);
    #endif

    int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
    return 0;
}