Üç nəfər Prostokvaşinodan
- Dayı Fyodor, Dayı Fyodor, mən seqment ağacı qurmağı öyrəndim.
- Gözlə, Şarik, mən məşğulam.
- Yaxşı Dayı Fyodor, bax gör necə kod yazmışam:
int build(int v, int left, int right) {
if (left == right) {
t[v] = a[left];
return 0;
}
int mid = (left+right) / 2;
build(v*2, left, mid);
build(v*2+1, mid+1, right);
t[v] = max(t[v*2], t[v*2+1]);
return 0;
}
int get_max(int v, int left, int right, int lpos, int rpos) {
if (left == lpos right == rpos)
return t[v];
if (lpos > rpos)
return -1;
int mid = (left+right) / 2;
return max(get_max(v*2, left, mid, lpos, min(rpos, mid)),
get_max(v*2+1, mid+1, right, max(lpos, mid+1), rpos));
}
- Yaxşı, Şarik, əgər sən bu mövzunu belə yaxşı başa düşmüsənsə, mən sənə N müsbət olmayan ədədlərdən ibarət bir massiv və bir k verim, sən də mənə deyərsən neçə belə cütlük var l; r (1 ≤ l ≤ r ≤ N), ki, aşağıdakı şəkildə çağırılan funksiya
get_max(1, 1, N, l, r)
dəyərini k bərabər qaytarır. Bunun əvvəlində funksiyanın çağırıldığını qəbul etmək olar
build(1, 1, N)
- Yaxşı, Dayı Fyodor!
Giriş verilənləri
Birinci sətirdə N (1 ≤ N ≤ 10^6) – massivdəki elementlərin sayı və k (1 ≤ k ≤ 10^9) – funksiyanın qaytarmalı olduğu dəyər verilir. Növbəti sətirdə N ədəd verilir ki, bunlar 10^9 keçməyən müsbət olmayan ədədlərdir – massiv elementləri.
Çıxış verilənləri
Tək bir ədəd çıxarın – məsələnin cavabı.