Can someone tell me what's the time complexity of this code? I thought it's O(N^2) because of vector erase but it gets AC 332397335.

#include <bits/stdc++.h>
 
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ln '\n'
#define sep ' '
#define ve vector

using namespace std;
 
using pii = pair<int, int>;
using ll  = long long;
using ull = unsigned ll;
using ld  = long double;

constexpr int N=5e5+1;
int n,c,a[N],freq[N],freq2[N];
ve<int>q[N];

inline void solve()
{
  cin>>n>>c;
  for(int i=1;i<=n;++i)
  {
    cin>>a[i];
    freq2[i]=freq2[i-1];
    if(a[i]==c)++freq2[i];
  }

  int ans=freq2[n];

  for(int i=1;i<=n;++i)
  {
    int x=a[i];

    if(x==c)continue;

    freq[i]=(q[x].empty()?0:freq[q[x].back()])+1;

    q[x].push_back(i);

    while(!q[x].empty())
    {
      int j=q[x].front();
      int c1=freq[i]-freq[j]+1;
      int c2=freq2[i]-freq2[j-1];
      int c=c1-c2;

      ans=max(ans,freq2[n]+c);

      if(c>0)break;

      q[x].erase(q[x].begin(),q[x].begin()+1);
    }
  }

  cout<<ans<<ln;
}

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

Some solutions to atcoder problems will not get AC without optimization pragmas despite being optimal in time complexity:

Without pragmas: link

With pragmas: link

Hi codeforces community!

So I was solving this problem: 1703G - Good Key, Bad Key

I wrote first solution: 283940469 ~ TLE

I wrote second solution: 283940935 ~ AC

Two programs are very similar to each other so i will list most notable differences between them:

• First solution uses C-array a of size N = 1e5 defined globally. Second solution uses vector of size n which is defined for each test case
• First solution uses vector<vector<ll>> dp, with N rows and each row is of size 31 and for each test it fills every row with vector<ll>(31, -1). Second solution uses similar dp vector but has n rows and is defined in the solve function
• First solution accesses variables n, k, dp from the global scope. Second solution passes references to vectors as parameters and variable k also as parameters for each recursive call.

I sincerely thought first solution would be faster than second solution.

So, my question is why is that first solution gets TLE but second solution gets AC?