Վերին սահման (Upper bound)
Տրված է աճման կարգով դասավորված
n ամբողջ թվերից կազմված զանգված, և ձեզ խնդրում են պատասխանել q հարցումների: Յուրաքանչյուր հարցում ձևակերպված է հետևյալ կերպ. «Ո՞րն է առաջին թվը, որը մեծ է x-ից տվյալ ցուցակում»։Մուտք
Մուտքի առաջին տողում տրված են երկու ամբողջ թվեր
n (2 ≤ n ≤ ) և q (1 ≤ q ≤ )։Մուտքի հաջորդ տողում տրված են
n ամբողջ թվեր ( ≤ ≤ ) աճման կարգով։Մուտքի վերջին տողում տրված են
q հարցումներ ( ≤ < )։Ելք
Ծրագիրը պետք է տպի
q տող։ Յուրաքանչյուր տողում` համապատասխան հարցման պատասխանը։Օրինակ
Մուտք | Ելք |
6 3
2 7 9 10 20 30
8 20 1 | 9
30
2 |
Հուշում
Երկուական որոնման (Binary Search) դասական իրականացման դեպքում օգտագործվում է
[l; r) միջակայքը, որտեղ l-ը ներառված է, իսկ r-ը՝ ոչ։ Որոշ դեպքերում, սակայն, կարող է պահանջվել (l; r] տարբերակը՝ ներառելով r-ը, իսկ l-ը՝ ոչ։ Սա կպահանջի փոփոխություններ l, r և mid արժեքները հաշվարկի մեջ։Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB