fork download
copy 
  1. #include <iostream>
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4.  
  5. int main() {
  6. 	int n ; cin>>n; int k ; cin>>k;
  7. 	vector<int>arr(n);
  8. 	for(int i =0 ; i<n;i++){
  9. 		cin>>arr[i];
  10. 	}
  11. 	vector<int>pge(n,0);
  12.  
  13.  
  14. 	stack<int>s;
  15. 	for(int i = n-1 ;i>=0;i--){
  16. 		while(!s.empty() && arr[i]>=arr[s.top()]){
  17. 			pge[s.top()]=i;
  18. 			s.pop();
  19. 		}
  20. 		s.push(i);
  21. 	}
  22. 	while(!s.empty()) s.pop();
  23. 	vector<int>nge(n,n-1);
  24. 	for(int i = 0 ; i<n;i++){
  25. 		while(!s.empty() && arr[i]>=arr[s.top()]){
  26. 			nge[s.top()]=i;
  27. 			s.pop();
  28. 		}
  29. 		s.push(i);
  30. 	}
  31. 	for(int i = 0 ; i<n;i++)cout<<nge[i];
  32. 	cout<<endl;
  33.  
  34. 	int sum = 0 ; 
  35. 	for(int i = 0 ;i<n;i++){
  36. 		if(arr[i]==k){
  37. 		 int x = i-(pge[i]+1);
  38. 		 int y = (nge[i]-1)-i;
  39. 		 sum+=x+y+x*y+1;
  40. 		}
  41. 	}
  42. 	cout<<sum;
  43.  
  44.  
  45. 	// your code goes here
  46. 	return 0;
  47. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
8 3
8 2 1 3 4 5 1 10
stdout
copy 
73345777
3
https://ideone.com/hlm5hC
language:
C++ (gcc 8.3)
created:
8 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!