fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10.  
  11. 	public static int N;
  12. 	public static int[] leftSmaller(int[] arr) {
  13.         int n = arr.length;
  14.         int[] left = new int[n];
  15.         Stack<Integer> st = new Stack<>();
  16.  
  17.         for (int i = 0; i < n; i++) {
  18.  
  19.             while (!st.isEmpty() && arr[st.peek()] >= arr[i]) {
  20.                 st.pop();
  21.             }
  22.  
  23.             left[i] = st.isEmpty() ? -1 : st.peek();
  24.  
  25.             st.push(i);
  26.         }
  27.  
  28.         return left;
  29.     }
  30.  
  31.     public static int[] rightSmaller(int[] arr) {
  32.         int n = arr.length;
  33.         int[] right = new int[n];
  34.         Stack<Integer> st = new Stack<>();
  35.  
  36.         for (int i = n - 1; i >= 0; i--) {
  37.  
  38.             while (!st.isEmpty() && arr[st.peek()] > arr[i]) {
  39.                 st.pop();
  40.             }
  41.  
  42.             right[i] = st.isEmpty() ? N : st.peek();
  43.  
  44.             st.push(i);
  45.         }
  46.  
  47.         return right;
  48.     }
  49. 	public static void main (String[] args) throws java.lang.Exception
  50. 	{
  51. 		// your code goes here
  52. 		int[] arr = {2, 4, 5, 3, 2, 1, 6, 3, 1};
  53. 		N = arr.length;
  54. 		int[] contribution = new int[N];
  55.  
  56. 		int[] left_smaller = leftSmaller(arr);
  57. 		int[] right_smaller = rightSmaller(arr);
  58.  
  59. 		long ans = 0;
  60.  
  61. 		for(int i = 0; i < N; i++){
  62. 			int i1 = left_smaller[i];
  63. 			int j1 = right_smaller[i];
  64. 			i1++;
  65. 			j1--;
  66.  
  67. 			int x = Math.abs(i-i1);
  68. 			int y = Math.abs(i-j1);
  69.  
  70. 			contribution[i] = (x+1)*(y+1);
  71.  
  72. 			ans += 1L* contribution[i] * arr[i];
  73.  
  74. 		}
  75. 		System.out.print(ans);
  76. 	}
  77. }
Success #stdin #stdout 0.07s 54520KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
79
https://ideone.com/uaMF7Q
language:
Java (HotSpot 12)
created:
1 hour 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!