TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P3454
  • Problem
  • P3454【HN Training 2015 Round9】 DATE
    Limits : Time Limit : - MS   Memory Limit : 265536 KB  SPJ
    Judgment Tips : 1s,265535
    Description

    给定一个长度为n的序列a[i],q次提问,对于每次提问(L,R,F),随机生成一个1......(R-L+1)之间的整数K,在a[L]......a[R]中随机抽出K个a[p[1]]......a[p[k]],求a[p[1]]......a[p[k]]都大于F的概率的100000倍是多少

    Input Format

    第一行两个整数n m

    第二行n个整数,第i个整数表示a[i]

    接下来m行每行三个整数L[i],R[i],F[i]

    Output Format

    m行,每行一个实数,保留两位小数

    Sample Input

    10 10
    8 9 9 9 3 7 9 8 9 1
    10 10 1
    4 5 3
    1 4 9
    2 4 9
    2 8 9
    3 9 9
    3 6 3
    1 7 8
    1 2 9
    3 5 9

    Sample Output

    100000.00
    100000.00
    37500.00
    100000.00
    14285.71
    14285.71
    100000.00
    23809.52
    25000.00
    33333.33

    Hint

    1 <= n <= 100000 , 1 <= L[i] <=  R[i] <=  100000, a[i] <= 100000