Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.Scanner;
- public class SolutionWithFenwick {
- static int activityNotifications(int[] expenditure, int d) {
- BIT fenwick = new BIT(201);
- int index=0;
- int count=0;
- for(int i = 0; i<d;i++){
- fenwick.update(expenditure[i],1);
- }
- for(int j = d; j<expenditure.length;j++){
- double median;
- if (d%2!=0){
- median = binarnoZaNeparni(fenwick,d/2);
- }else {
- double element1= binarnoZaParni(fenwick,d/2);
- double element2 = binarnoZaParni(fenwick, (d/2)+1);
- median = (element1+element2)/2.0;
- }
- if (expenditure[j]>=2*median){
- count++;
- }
- fenwick.update(expenditure[index], -1);
- index++;
- fenwick.update(expenditure[j],1);
- }
- return count;
- }
- private static int binarnoZaNeparni (BIT fenwick, int indeks){
- int lo = 0;
- int hi = 201;
- while (lo<hi){
- int mid = lo + (hi-lo) / 2;
- if (fenwick.sum(mid)>indeks){
- hi=mid;
- }else {
- lo=mid+1;
- }
- }
- return lo;
- }
- private static int binarnoZaParni (BIT fenwick, int indeks){
- int lo = 0;
- int hi = 200;
- while (lo<hi){
- int mid = lo + (hi-lo) / 2;
- if (fenwick.sum(mid)>=indeks){
- hi=mid;
- }else {
- lo=mid+1;
- }
- }
- return lo;
- }
- public static void main(String[] args) {
- Scanner in = new Scanner(System.in);
- int n = in.nextInt();
- int d = in.nextInt();
- int[] expenditure = new int[n];
- for(int expenditure_i = 0; expenditure_i < n; expenditure_i++){
- expenditure[expenditure_i] = in.nextInt();
- }
- int result = activityNotifications(expenditure, d);
- System.out.println(result);
- in.close();
- }
- private static class BIT {
- int size;
- int[] table;
- public BIT (int size){
- table = new int[size];
- this.size=size;
- }
- public void update (int i, int delta){
- while (i<size){
- table[i] += delta;
- i+=Integer.lowestOneBit(i);
- }
- }
- public int sum (int i){
- int sum = 0;
- while (i>0){
- sum+=table[i];
- i-=Integer.lowestOneBit(i);
- }
- return sum;
- }
- public int rangeSum (int i, int j){
- return sum(j)-sum(i-1);
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement