Advertisement
Guest User

Untitled

a guest
Jan 23rd, 2018
64
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.75 KB | None | 0 0
  1. import java.util.Scanner;
  2.  
  3. public class SolutionWithFenwick {
  4.  
  5.  
  6.     static int activityNotifications(int[] expenditure, int d) {
  7.         BIT fenwick = new BIT(201);
  8.         int index=0;
  9.         int count=0;
  10.  
  11.         for(int i = 0; i<d;i++){
  12.             fenwick.update(expenditure[i],1);
  13.         }
  14.         for(int j = d; j<expenditure.length;j++){
  15.             double median;
  16.             if (d%2!=0){
  17.                 median = binarnoZaNeparni(fenwick,d/2);
  18.  
  19.  
  20.             }else {
  21.                 double element1= binarnoZaParni(fenwick,d/2);
  22.                 double element2 = binarnoZaParni(fenwick, (d/2)+1);
  23.                 median = (element1+element2)/2.0;
  24.             }
  25.  
  26.             if (expenditure[j]>=2*median){
  27.                 count++;
  28.             }
  29.  
  30.             fenwick.update(expenditure[index], -1);
  31.             index++;
  32.             fenwick.update(expenditure[j],1);
  33.         }
  34.  
  35.         return count;
  36.     }
  37.  
  38.     private static int binarnoZaNeparni (BIT fenwick, int indeks){
  39.         int lo = 0;
  40.         int hi = 201;
  41.  
  42.         while (lo<hi){
  43.             int mid = lo + (hi-lo) / 2;
  44.             if (fenwick.sum(mid)>indeks){
  45.                 hi=mid;
  46.             }else {
  47.                 lo=mid+1;
  48.             }
  49.  
  50.         }
  51.  
  52.         return lo;
  53.  
  54.     }
  55.  
  56.     private static int binarnoZaParni (BIT fenwick, int indeks){
  57.         int lo = 0;
  58.         int hi = 200;
  59.  
  60.         while (lo<hi){
  61.             int mid = lo + (hi-lo) / 2;
  62.             if (fenwick.sum(mid)>=indeks){
  63.                 hi=mid;
  64.             }else {
  65.                 lo=mid+1;
  66.             }
  67.         }
  68.         return lo;
  69.  
  70.     }
  71.     public static void main(String[] args) {
  72.         Scanner in = new Scanner(System.in);
  73.         int n = in.nextInt();
  74.         int d = in.nextInt();
  75.         int[] expenditure = new int[n];
  76.         for(int expenditure_i = 0; expenditure_i < n; expenditure_i++){
  77.             expenditure[expenditure_i] = in.nextInt();
  78.         }
  79.         int result = activityNotifications(expenditure, d);
  80.         System.out.println(result);
  81.         in.close();
  82.     }
  83.  
  84.     private static class BIT {
  85.         int size;
  86.         int[] table;
  87.  
  88.         public BIT (int size){
  89.             table = new int[size];
  90.             this.size=size;
  91.         }
  92.  
  93.         public  void update (int i, int delta){
  94.  
  95.             while (i<size){
  96.                 table[i] += delta;
  97.                 i+=Integer.lowestOneBit(i);
  98.             }
  99.         }
  100.  
  101.         public int sum (int i){
  102.             int sum = 0;
  103.             while (i>0){
  104.                 sum+=table[i];
  105.                 i-=Integer.lowestOneBit(i);
  106.             }
  107.             return sum;
  108.         }
  109.  
  110.         public int rangeSum (int i, int j){
  111.  
  112.             return sum(j)-sum(i-1);
  113.         }
  114.     }
  115. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement