Advertisement
PloadyFree

Useless SQRT with probs

Nov 25th, 2018
335
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 6.40 KB | None | 0 0
  1. import java.io.OutputStream;
  2. import java.io.IOException;
  3. import java.io.InputStream;
  4. import java.io.OutputStream;
  5. import java.io.PrintWriter;
  6. import java.util.Arrays;
  7. import java.io.BufferedWriter;
  8. import java.util.InputMismatchException;
  9. import java.io.IOException;
  10. import java.io.Writer;
  11. import java.io.OutputStreamWriter;
  12. import java.io.InputStream;
  13.  
  14. /**
  15.  * Built using CHelper plug-in
  16.  * Actual solution is at the top
  17.  *
  18.  * @author Rustam Musin (t.me/musin_acm)
  19.  */
  20. public class Main {
  21.     public static void main(String[] args) {
  22.         InputStream inputStream = System.in;
  23.         OutputStream outputStream = System.out;
  24.         InputReader in = new InputReader(inputStream);
  25.         OutputWriter out = new OutputWriter(outputStream);
  26.         TaskIFence solver = new TaskIFence();
  27.         solver.solve(1, in, out);
  28.         out.close();
  29.     }
  30.  
  31.     static class TaskIFence {
  32.         int n;
  33.         double[] pByIndex;
  34.         int BLOCK_SIZE = 350;
  35.         int blockCount;
  36.         double[] blockP1;
  37.         boolean[] active;
  38.  
  39.         public void solve(int testNumber, InputReader in, OutputWriter out) {
  40.             out.printFormat("%.20f", solve(in));
  41.         }
  42.  
  43.         double solve(InputReader in) {
  44.             n = in.readInt();
  45.             Action[] actions = new Action[2 * n];
  46.             for (int i = 0; i < n; i++) {
  47.                 int l = in.readInt();
  48.                 int r = in.readInt();
  49.                 double p = in.readInt() / 100.0;
  50.                 actions[i * 2] = new Action(i, true, l, p);
  51.                 actions[i * 2 + 1] = new Action(i, false, r, p);
  52.             }
  53.             Arrays.sort(actions);
  54.             int[] indexMap = new int[n];
  55.             Arrays.fill(indexMap, -1);
  56.             int actionCount = 0;
  57.             for (int i = 0; i < 2 * n; i++) {
  58.                 Action action = actions[i];
  59.                 if (action.appears) {
  60.                     indexMap[action.index] = actionCount++;
  61.                 }
  62.             }
  63.             for (int i = 0; i < 2 * n; i++) {
  64.                 Action action = actions[i];
  65.                 action.index = indexMap[action.index];
  66.             }
  67.             pByIndex = new double[actionCount];
  68.             for (Action action : actions) {
  69.                 pByIndex[action.index] = action.p;
  70.             }
  71.             blockCount = (n + BLOCK_SIZE - 1) / BLOCK_SIZE;
  72.             blockP1 = new double[blockCount];
  73.             active = new boolean[n];
  74.             double ans = 0;
  75.             int lastX = -1;
  76.             for (Action a : actions) {
  77.                 if (lastX != -1) {
  78.                     ans += getAnswer() * (a.x - lastX);
  79.                 }
  80.                 lastX = a.x;
  81.                 active[a.index] = a.appears;
  82.                 recalc(a.index / BLOCK_SIZE);
  83.             }
  84.             return ans;
  85.         }
  86.  
  87.         void recalc(int blockIndex) {
  88.             int l = blockIndex * BLOCK_SIZE;
  89.             int r = Math.min(n, l + BLOCK_SIZE);
  90.             double p1 = 0;
  91.             for (int i = l; i < r; i++) {
  92.                 if (active[i]) {
  93.                     double p = pByIndex[i];
  94.                     p1 = p1 * (1 - p) + (1 - p1) * p;
  95.                 }
  96.             }
  97.             blockP1[blockIndex] = p1;
  98.         }
  99.  
  100.         double getAnswer() {
  101.             double p1 = 0;
  102.             for (int i = 0; i < blockCount; i++) {
  103.                 double p = blockP1[i];
  104.                 p1 = p1 * (1 - p) + (1 - p1) * p;
  105.             }
  106.             return p1;
  107.         }
  108.  
  109.         class Action implements Comparable<Action> {
  110.             int index;
  111.             boolean appears;
  112.             int x;
  113.             double p;
  114.  
  115.             Action(int i, boolean appears, int x, double p) {
  116.                 index = i;
  117.                 this.appears = appears;
  118.                 this.x = x;
  119.                 this.p = p;
  120.             }
  121.  
  122.             public int compareTo(Action o) {
  123.                 return Integer.compare(x, o.x);
  124.             }
  125.  
  126.         }
  127.  
  128.     }
  129.  
  130.     static class OutputWriter {
  131.         private final PrintWriter writer;
  132.  
  133.         public OutputWriter(OutputStream outputStream) {
  134.             writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
  135.         }
  136.  
  137.         public OutputWriter(Writer writer) {
  138.             this.writer = new PrintWriter(writer);
  139.         }
  140.  
  141.         public void printFormat(String format, Object... objects) {
  142.             writer.printf(format, objects);
  143.         }
  144.  
  145.         public void close() {
  146.             writer.close();
  147.         }
  148.  
  149.     }
  150.  
  151.     static class InputReader {
  152.         private InputStream stream;
  153.         private byte[] buf = new byte[1024];
  154.         private int curChar;
  155.         private int numChars;
  156.         private InputReader.SpaceCharFilter filter;
  157.  
  158.         public InputReader(InputStream stream) {
  159.             this.stream = stream;
  160.         }
  161.  
  162.         public int read() {
  163.             if (numChars == -1) {
  164.                 throw new InputMismatchException();
  165.             }
  166.             if (curChar >= numChars) {
  167.                 curChar = 0;
  168.                 try {
  169.                     numChars = stream.read(buf);
  170.                 } catch (IOException e) {
  171.                     throw new InputMismatchException();
  172.                 }
  173.                 if (numChars <= 0) {
  174.                     return -1;
  175.                 }
  176.             }
  177.             return buf[curChar++];
  178.         }
  179.  
  180.         public int readInt() {
  181.             int c = read();
  182.             while (isSpaceChar(c)) {
  183.                 c = read();
  184.             }
  185.             int sgn = 1;
  186.             if (c == '-') {
  187.                 sgn = -1;
  188.                 c = read();
  189.             }
  190.             int res = 0;
  191.             do {
  192.                 if (c < '0' || c > '9') {
  193.                     throw new InputMismatchException();
  194.                 }
  195.                 res *= 10;
  196.                 res += c - '0';
  197.                 c = read();
  198.             } while (!isSpaceChar(c));
  199.             return res * sgn;
  200.         }
  201.  
  202.         public boolean isSpaceChar(int c) {
  203.             if (filter != null) {
  204.                 return filter.isSpaceChar(c);
  205.             }
  206.             return isWhitespace(c);
  207.         }
  208.  
  209.         public static boolean isWhitespace(int c) {
  210.             return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
  211.         }
  212.  
  213.         public interface SpaceCharFilter {
  214.             public boolean isSpaceChar(int ch);
  215.  
  216.         }
  217.  
  218.     }
  219. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement