fork(1) download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // my choco pie
  5.  
  6. #define ft first
  7. #define sd second
  8. #define pb push_back
  9. #define mp make_pair
  10. #define PII pair<int,int>
  11. #define all(x) x.begin(),x.end()
  12. #define VI vector<int>
  13. #define VII vector<pair<int,int> >
  14. #define VL vector<long long int >
  15. #define VLL vector<pair<long long ,long long > >
  16. #define PLL pair<long long ,long long >
  17. #define itr iterator
  18. #define fill(x,v) fill(all(x),v)
  19.  
  20. // my fastest car series
  21.  
  22. //#define scan(x) scanf("%d",&x)
  23. #define print(x) printf("%d\n",x)
  24. #define scanll(x) scanf("%lld",&x)
  25. #define printll(x) printf("%lld\n",x)
  26. #define ms(x) memset(x,0,sizeof(x))
  27.  
  28.  
  29. // data pies
  30.  
  31. #define ll long long int
  32. #define li long int
  33. #define ff float
  34. #define db double
  35.  
  36.  
  37. // loopi loops
  38.  
  39. #define rep(i,a,b) for(i=a;i<b;i++)
  40. #define repr(i,a,b) for(i=a;i>=b;i--)
  41.  
  42.  
  43. // debugger
  44. #define print_v(x) for(int i=0;i<x.size();i++) cout << x[i] << " " 
  45. #define debug(x) cout << "#debug" << " " << x << endl
  46.  
  47. #define MOD 1000000007
  48.  
  49. int random_long(int digit=8)
  50. {
  51.    int len=digit;
  52.    int x=0;
  53.    for ( int i = 0; i < len; ++i )
  54.    {
  55.     int dig = rand() % 10;
  56.     while ( x == 0 && dig == 0 )
  57.       dig = rand() % 10;
  58.     x = x * 10 + dig;
  59.   }
  60.    return x;
  61. }
  62.  
  63. int random(int l, int r)
  64. {
  65.     int diff = r - l + 1;
  66.  
  67.     return l+random_long()%diff;
  68.  
  69. }
  70. inline void scan(int &a)
  71. {
  72.     register int c;
  73.     a = 0;
  74. 	do c = getchar_unlocked(); while(c < '0');
  75. 	do{
  76. 		a = (a << 1) + (a << 3) + c - '0';
  77. 		c = getchar_unlocked();
  78. 	}while(c >= '0');
  79. }
  80. int main(){
  81. 	int t;
  82. 	t=1;
  83. 	while (t--) {
  84. 		int n , i , val;
  85. 		scan(n);
  86. 		VII arr(n+1,mp(0,0));
  87. 		rep(i,1,n+1){
  88. 			scan( arr[i].ft ) ;
  89. 			arr[i].sd = i ;
  90. 		}
  91. 		sort( all(arr) );
  92.   		set<int> s ;
  93. 		ll ans = 0 ;
  94. 		i = n ;
  95. 		while (i>=1) {
  96. 			int x = arr[i].ft ;
  97. 			int savei = i ;
  98. 			VI tt;
  99. 			while (i>=1 && x == arr[i].ft){
  100. 				tt.pb( arr[i].sd );
  101. 				i--;
  102. 			}
  103. 			reverse( all(tt) ); 
  104. 			i = savei;
  105. 			while ( i>=1 && x == arr[i].ft ) {
  106.  
  107. 				val = arr[i].sd;
  108. 				if( s.empty()){
  109. 					val = 1;
  110. 				}else{
  111. 					set <int> :: itr it = lower_bound(all(s),arr[i].sd);
  112. 					if ( it!=s.begin() ){
  113. 						--it;
  114. 						val = (*it)+1;
  115. 					}else {
  116. 						val = 1;
  117. 					} 
  118. 				}
  119. 				if( val != arr[i].sd ){
  120. 					ans += (lower_bound(all(tt), arr[i].sd) - lower_bound(all(tt), val) ) ;				
  121. 				}				
  122. 				i--; 
  123. 			}
  124. 			i = savei;
  125. 			while ( i>=1 && x==arr[i].ft ){
  126. 				s.insert( arr[i].sd );
  127. 				i--;
  128. 			}	
  129. 		}
  130. 		printll(2*ans);		
  131. 	}
  132. 	return 0;
  133. }
Time limit exceeded #stdin #stdout 5s 3300KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/D2JJqp
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
secret

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!