codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

2125D.md (1532B)


      1 Source: https://codeforces.com/problemset/problem/2125/D
      2 
      3 D. Segments Covering
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 There is a linear strip divided into $m$ cells, numbered from $1$ to $m$ from left to right.
     22 
     23 You are given $n$ segments. Each segment is defined by four numbers: $l$, $r$, $p$ and $q$ — the segment covers cells from $l$ to $r$ inclusively and exists with probability $\frac{p}{q}$ (independently).
     24 
     25 Your task is to calculate the probability that each cell is covered by exactly one segment.
     26 
     27 Input
     28 
     29 The first line contains two integers $n$ and $m$ ($1 \le n, m \le 2 \cdot 10^5$).
     30 
     31 Then $n$ lines follow. The $i$-th of them contains four integers $l_i$, $r_i$, $p_i$ and $q_i$ ($1 \le l_i \le r_i \le m$; $1 \le p_i \lt q_i \lt 998244353$).
     32 
     33 Output
     34 
     35 Print a single integer — the probability that each cell is covered by exactly one segment, taken modulo $998244353$.
     36 
     37 Formally, the probability can be expressed as an irreducible fraction $\frac{x}{y}$. You have to print the value of $x \cdot y^{-1} \bmod 998244353$, where $y^{-1}$ is an integer such that $y \cdot y^{-1} \bmod 998244353 = 1$.
     38 
     39 Examples
     40 
     41 Input
     42 
     43 ```
     44 3 3
     45 
     46 1 2 1 3
     47 
     48 3 3 1 2
     49 
     50 1 3 2 3
     51 ```
     52 
     53 Output
     54 
     55 ```
     56 610038216
     57 ```
     58 
     59 Input
     60 
     61 ```
     62 2 3
     63 
     64 1 2 1 2
     65 
     66 2 3 1 2
     67 ```
     68 
     69 Output
     70 
     71 ```
     72 0
     73 ```
     74 
     75 Input
     76 
     77 ```
     78 8 5
     79 
     80 1 3 1 2
     81 
     82 1 5 1 6
     83 
     84 1 4 4 5
     85 
     86 5 5 1 7
     87 
     88 4 5 1 2
     89 
     90 4 5 2 5
     91 
     92 3 3 2 7
     93 
     94 1 2 1 3
     95 ```
     96 
     97 Output
     98 
     99 ```
    100 94391813
    101 ```
    102 
    103 Note
    104 
    105 In the first example, the probability is equal to $\frac{5}{18}$.