fork download 
  1. import java.util.*;
  2.  
  3. class Main {
  4.     public static void main(String[] args) {
  5.         Scanner sc = new Scanner(System.in);
  6.         int n = sc.nextInt();
  7.         int[] p = new int[n+1];
  8.  
  9.         for(int i=1;i<=n;i++) {
  10.         p[i] = sc.nextInt();
  11.         }
  12.         for(int i=1;i<=n;i++){
  13.             HashSet<Integer> med = new HashSet<>();
  14.  
  15.             for(int l=1;l<=i;l++){
  16.                 TreeMap<Integer,Integer> left = new TreeMap<>();
  17.                 TreeMap<Integer,Integer> right = new TreeMap<>();
  18.                 int leftSize = 0, rightSize = 0;
  19.  
  20.                 for(int r=l;r<=i;r++){
  21.                     int x = p[r];
  22.  
  23.                     if(leftSize==0 || x<=left.lastKey()){
  24.                         left.put(x, left.getOrDefault(x,0)+1);
  25.                         leftSize++;
  26.                     } else {
  27.                         right.put(x, right.getOrDefault(x,0)+1);
  28.                         rightSize++;
  29.                     	}
  30.  
  31.                     while(leftSize > rightSize+1){
  32.                         int v = left.lastKey();
  33.                         int c = left.get(v);
  34.                         if(c==1) left.remove(v);
  35.                         else left.put(v,c-1);
  36.                         leftSize--;
  37.  
  38.                         right.put(v, right.getOrDefault(v,0)+1);
  39.                         rightSize++;
  40.                     }
  41. 						while(rightSize > leftSize){
  42.                         int v = right.firstKey();
  43.                         int c = right.get(v);
  44.                         if(c==1) right.remove(v);
  45.                         else right.put(v,c-1);
  46.                         rightSize--;
  47.  
  48.                         left.put(v, left.getOrDefault(v,0)+1);
  49.                         leftSize++;
  50.                     }
  51. 						if(r-l+1 >= 2)
  52.                         med.add(left.lastKey());
  53.                 }
  54.             }
  55.  
  56.             System.out.print(med.size());
  57.             if(i!=n) System.out.print(" ");
  58.         }
  59.         System.out.println();
  60.     }
  61.  
  62. }
  63.  
Success #stdin #stdout 0.17s 56776KB
comments (?)
stdin 
5
3 1 4 5 2
stdout 
0 1 2 3 4
https://ideone.com/Yez4dF
language:
Java (HotSpot 12)
created:
7 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!