fork download
copy 
  1. import java.util.*;
  2. import static java.util.Arrays.*;
  3.  
  4. public class BottlesOnShelf {
  5.  
  6.     public int getNumBroken(int N, int[] left, int[] right, int[] damage) {
  7.         int M = damage.length;
  8.         int[] xs = new int[2 * M];
  9.         for (int i = 0; i < M; i++) {
  10.             xs[2 * i] = --left[i];
  11.             xs[2 * i + 1] = right[i];
  12.         }
  13.         sort(xs);
  14.         L[] on = new L[2 * M - 1];
  15.         for (int i = 0; i < 2 * M - 1; i++)
  16.             on[i] = new L();
  17.         for (int i = 0; i < 2 * M - 1; i++)
  18.             if (xs[i] < xs[i + 1])
  19.                 for (int j = 0; j < M; j++)
  20.                     if (left[j] <= xs[i] && xs[i + 1] <= right[j])
  21.                         on[i].add(j);
  22.  
  23.         int ret = 0;
  24.         for (int i = 0; i < 2 * M - 1; i++) {
  25.             int m = on[i].size();
  26.             long s = 0;
  27.             loop: for (int j = 1; j < (1 << m); j++) {
  28.                 L l = new L();
  29.                 for (int k = 0; k < m; k++)
  30.                     if ((j & (1 << k)) > 0)
  31.                         l.add(on[i].get(k));
  32.  
  33.                 int gcd = 0;
  34.                 for (int k : l)
  35.                     gcd = gcd(damage[k], gcd);
  36.  
  37.                 int lcm = gcd;
  38.                 for (int k : l) {
  39.                     int d = damage[k] / gcd(damage[k], lcm);
  40.                     if(Integer.MAX_VALUE / d < lcm)
  41.                         continue loop;
  42.                     lcm *= d;
  43.                 }
  44.  
  45.                 s += (xs[i + 1] / lcm - xs[i] / lcm)
  46.                         * (Integer.bitCount(j) % 2 == 0 ? -1 : 1);
  47.             }
  48.             ret += s;
  49.         }
  50.         return ret;
  51.     }
  52.  
  53.     class L extends ArrayList<Integer> {};
  54.  
  55.     int gcd(int x, int y) {
  56.         return y == 0 ? x : gcd(y, x % y);
  57.     }
  58. }
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/xBUqb
language:
Java (HotSpot 12)
created:
14 years 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!