fork download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. using namespace std ;
  5.  
  6. #define MAX 100001
  7. int N,arr[MAX],st[4*MAX],ans[MAX];
  8. inline void sc(int &a)
  9. {
  10.     register int c;
  11.     a = 0;
  12.     do c = getchar_unlocked(); while(c < '0');
  13.     do{
  14. 	a = (a << 1) + (a << 3) + c - '0';
  15. 	c = getchar_unlocked();
  16.     }while(c >= '0');
  17. }
  18.  
  19. inline void buildst(int idx,int ss,int se){
  20.  
  21. 	if(ss == se){
  22. 		st[idx] = arr[ss] ;
  23. 		return ;
  24. 	}
  25. 	int mid = (ss+se)/2;
  26. 	buildst(2*idx,ss,mid);
  27. 	buildst(2*idx+1,mid+1,se);
  28. 	st[idx] = max(st[2*idx],st[2*idx+1]);
  29. }
  30.  
  31. inline int query(int idx,int ss,int se,int l,int r){
  32.  
  33. 	if(l > se || r < ss)
  34. 		return 0;
  35. 	if(l<=ss && se<=r)
  36. 		return st[idx] ;
  37. 	int mid = (ss+se)/2;
  38. 	return max(query(2*idx,ss,mid,l,r),query(2*idx+1,mid+1,se,l,r));
  39. }
  40.  
  41. inline int cal(int low,int high,int key){
  42.  
  43. 	int mid ;
  44. 	while(low<=high){
  45. 		mid = (low+high)/2;
  46. 		int f1 = query(1,1,N,low,mid);
  47. 		if(f1<key && (mid == N || (query(1,1,N,low,mid+1)>=key)))
  48. 			return mid ;
  49. 		else if(f1<key)
  50. 			low = mid+1;
  51. 		else
  52. 			high = mid-1;	
  53. 	}
  54. 	return 0;
  55. }
  56.  
  57. int main(){
  58.  
  59. 	sc(N);
  60. 	for(int i=1;i<=N;i++)
  61. 		sc(arr[i]) ;
  62.  
  63. 	buildst(1,1,N);
  64. 	long long x = 0;
  65. 	for(int i=1;i<=N;i++){
  66. 		ans[i] = cal(i+1,N,arr[i]);
  67. 		if(ans[i]!=0)
  68. 			ans[i] -= i;
  69. 		x += ans[i];	
  70. 	}
  71. 	printf("%lld\n",x);
  72. 	return 0;
  73. }
Success #stdin #stdout 0s 5648KB
comments (?)
stdin
copy 
6
10
3
7
4
12
2
stdout
copy 
5
https://ideone.com/TUrkFv
language:
C++14 (gcc 8.3)
created:
11 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!