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 [submission:332397335].↵
↵
<spoiler summary="Code">↵
~~~~~↵
#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;↵
}↵
↵
~~~~~↵
↵
</spoiler>↵
↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
#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;↵
}↵
↵
~~~~~↵
↵
</spoiler>↵
↵
↵
