fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define endl "\n"
  4. #define gc getchar_unlocked
  5. #define fo(i,n) for(i=0;i<n;i++)
  6. #define Fo(i,k,n) for(i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
  7. #define ll long long
  8. #define si(x)	scanf("%d",&x)
  9. #define sl(x)	scanf("%lld",&x)
  10. #define ss(s)	scanf("%s",s)
  11. #define pi(x)	printf("%d\n",x)
  12. #define pl(x)	printf("%lld\n",x)
  13. #define ps(s)	printf("%s\n",s)
  14. #define deb(x) cout << #x << "=" << x << endl
  15. #define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
  16. #define pb push_back
  17. #define mp make_pair
  18. #define F first
  19. #define S second
  20. #define all(x) x.begin(), x.end()
  21. #define clr(x) memset(x, 0, sizeof(x))
  22. #define sortall(x) sort(all(x))
  23. #define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
  24. #define PI 3.1415926535897932384626
  25. typedef pair<int, int>	pii;
  26. typedef pair<ll, ll>	pl;
  27. typedef vector<int>		vi;
  28. typedef vector<ll>		vl;
  29. typedef vector<pii>		vpii;
  30. typedef vector<pl>		vpl;
  31. typedef vector<vi>		vvi;
  32. typedef vector<vl>		vvl;
  33.  
  34. const int mod = 1000000007;
  35. const int N = 2e5+10, M = N;
  36.  
  37. int main() {
  38. 	ios_base::sync_with_stdio(false);
  39. 	cin.tie(NULL);
  40.     int t,x;
  41.     si(t);
  42.     fo(x,t)
  43.     {
  44.     	int i, k, p, q, r, x, y, u, v, m=0, n, j;
  45.     	si(n);
  46.     	int arr[n+2];
  47.     	map<pair<int,int>,int>mp;
  48.     	fo(i,n){
  49.     		si(arr[i]);
  50.     		m=max(m,arr[i]);
  51.     	}
  52.     	int pref[n+2][m+2],cnt[m+2];
  53.     	fo(i,m+1){
  54.     		cnt[i]=0;
  55.     	}
  56.     	fo(i,n){
  57.     		fo(j,m+1){
  58.     			pref[i][j]=0;
  59.     		}
  60.     	}
  61.     	fo(i,n){
  62.     		cnt[arr[i]]++;
  63.     	}
  64.  
  65.     	pref[0][arr[0]]=1;
  66.     	mp[{1,arr[0]}]=1;
  67.     	Fo(i,1,n){
  68.     		Fo(j,1,m+1){
  69.     			if(j == arr[i]){
  70.     				pref[i][j]=1;	
  71.     			}
  72.     			pref[i][j]+=pref[i-1][j];
  73.     			if(mp[{pref[i][j],j}] == 0)
  74.     				mp[{pref[i][j],j}]=i+1;
  75.     		}
  76.     	}
  77.     	int gloans=1,prev=0,ans,reqdcount,idx,maxi;
  78.     	fo(i,n-1){
  79.     		 ans=1;
  80.     			j=arr[i];
  81.     			reqdcount=cnt[j]-pref[i][j]+1;
  82.     			idx=mp[{reqdcount,j}]-1;
  83.     			if(idx>i){
  84.     				ans=2*pref[i][j];
  85.     				prev=ans;
  86.     				maxi=0;
  87.     				Fo(k,1,m+1){
  88.     					maxi=max(maxi,pref[idx-1][k]-pref[i][k]);
  89.     				}
  90.     				ans+=maxi;
  91.     				gloans=max(gloans,ans);
  92.     			}
  93.     	}
  94.     	cout<<gloans<<"\n";
  95.     }
  96. }
Success #stdin #stdout 0s 4376KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/q83VDg
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!