fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define pb push_back
  5. #define sz(a) (int)a.size()
  6.  
  7. const int mxN = (int)6e5+10;
  8. const int C = (int)1e5+10;
  9.  
  10. int n;
  11. stack<int> S;
  12. int lst[C], cnt[C];
  13. vector<int> v[C], D[C];
  14. int a[mxN], pr1[mxN], pr2[mxN], nx1[mxN], nx2[mxN];
  15.  
  16. void solve(){
  17. 	cin >> n; 
  18. 	for(int i = 0; i < n; i++){
  19. 		cin >> a[i]; cnt[a[i]]=0;
  20. 		v[a[i]].clear();
  21. 	}
  22.  
  23. 	fill(pr1,pr1+n,-1); fill(pr2,pr2+n,-1); fill(lst,lst+C,-1);
  24. 	for(int i = 0; i < n; i++) v[a[i]].pb(i), nx1[i]=nx2[i]=n;
  25.  
  26. 	S=stack<int>();
  27. 	for(int i = 0; i < n; i++){
  28. 		while(sz(S) and a[S.top()]>=a[i]) S.pop();
  29. 		if(sz(S)) pr1[i] = S.top();
  30. 		S.push(i);
  31. 	}
  32. 	S=stack<int>();
  33. 	for(int i = 0; i < n; i++){
  34. 		while(sz(S) and a[S.top()]<=a[i]) S.pop();
  35. 		if(sz(S)) pr2[i] = S.top();
  36. 		S.push(i);
  37. 	}
  38. 	S=stack<int>();
  39. 	for(int i = n-1; i >= 0; i--){
  40. 		while(sz(S) and a[S.top()]>=a[i]) S.pop();
  41. 		if(sz(S)) nx1[i] = S.top();
  42. 		S.push(i);
  43. 	}
  44. 	S=stack<int>();
  45. 	for(int i = n-1; i >= 0; i--){
  46. 		while(sz(S) and a[S.top()]<=a[i]) S.pop();
  47. 		if(sz(S)) nx2[i] = S.top();
  48. 		S.push(i);
  49. 	}
  50.  
  51. 	int ans = 0;
  52. 	for(int i = 0; i < n; i++){
  53. 		for(int x : D[a[i]]){
  54. 			int j = lst[x], k = -1, j2, k2;
  55. 			if(cnt[x]<sz(v[x])) k=v[x][cnt[x]];
  56. 			if(j==-1 or j<=pr2[i] or nx1[j]<=i) j=-1;
  57. 			if(k==-1 or nx2[i]<=k or pr1[k]>=i) k=-1;
  58. 			if(j==-1 and k==-1) continue;
  59.  
  60. 			if(j==-1) j2=max(pr2[i]+1,pr1[k]+1);
  61. 			else j2=max(pr2[i]+1,pr1[j]+1);
  62.  
  63. 			if(k==-1) k2 = min(nx2[i]-1, nx1[j]-1);
  64. 			else k2=min(nx2[i]-1,nx1[k]-1);
  65.  
  66. 			ans = max(ans, k2-j2+1);
  67. 		}
  68. 		cnt[a[i]]++; lst[a[i]]=i;
  69. 	}
  70. 	cout << ans << "\n";
  71. }
  72.  
  73. int main(){
  74.     ios_base::sync_with_stdio(false); cin.tie(0);
  75.     for(int i = 1; i < C; i++)
  76. 		for(int j = i; j < C; j+=i)
  77. 			D[j].pb(i);
  78.     int t = 1; //cin >> t;
  79.     while(t--) solve();		
  80. }
Success #stdin #stdout 0.07s 26732KB
comments (?)
stdin
copy 
8
10 4 20 19 29 16 30 17
stdout
copy 
4
https://ideone.com/FjIRv0
Largest subarray such that max%min = 0
language:
C++14 (gcc 8.3)
created:
2 days 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!