e-olymp4491 Трое из Простоквашино

Условие задачи:
— Дядя Федор, Дядя Федор, я научился строить дерево отрезков.
— Подожди, Шарик, я занят.
— Ну Дядя Федор, ну смотри какой я код написал:

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));
}

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));

}

— Ну хорошо, Шарик, раз ты так хорошо разобрался с этой темой, давай я тебе дам массив из [latex]n[/latex] неотрицательных чисел и число [latex]k[/latex], а ты мне скажешь сколько существует таких пар [latex]l;r \left ( 1\leq l\leq r\leq n \right ),[/latex] что функция, вызванная следующим образом:

[latex]get[/latex]_[latex]max(1, 1, n, l, r)[/latex]
вернет значение равное [latex]k[/latex]. Можно считать, что перед этим была вызвана функция

[latex]build(1, 1, n)[/latex]

— Хорошо, Дядя Федор!

Входные данные:
В первой строке находятся число [latex]n \left ( 1\leq n\leq 10^{6} \right )[/latex] — количество элементов в массиве и [latex]k \left ( 1\leq k\leq 10^{9} \right )[/latex] — значение, которое должна вернуть функция. В следующей строке находится [latex]n[/latex] неотрицательных чисел, не превышающих [latex]10^{9}[/latex] — элементы массива.

Выходные данные:
Выведите единственное число – ответ на задачу.

Тесты:

Входные данные			Выходные данные
[latex]n[/latex]	[latex]k[/latex]	[latex]elem[/latex]_[latex]tree[][/latex]	[latex]ans[/latex]
5	3	1 2 3 2 3	11
10	6	1 4 7 6 2 4 1 9 6 6	7
20	15	5 2 4 7 15 3 15 20 31 15 15 1 23 4 8 15 1 2 15 6	43

Код программы:

import java.util.*;

public class Main
{
  public static void main(String[] args) 
  {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    int k = in.nextInt();
    int[] elem_tree = new int[n];
    int ans=0, left=0, right=0;
    for(int i=0; i<n; i++){
    	elem_tree[i]=in.nextInt();
    	if (elem_tree[i]==k){
    		ans+=i-left+1;
    		right=i;
    	}
    	else{
    		if(elem_tree[i]>k){
        			right=0;
        			left=i+1;
    		}
    		else if(elem_tree[i]<k && right!=0) ans+=right-left+1;
    	}
    }
    System.out.println(ans);
  }
}

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner in = new Scanner(System.in);

int n = in.nextInt();

int k = in.nextInt();

int[] elem_tree = new int[n];

int ans=0, left=0, right=0;

for(int i=0; i<n; i++){

elem_tree[i]=in.nextInt();

if (elem_tree[i]==k){

ans+=i-left+1;

right=i;

}

else{

if(elem_tree[i]>k){

right=0;

left=i+1;

}

else if(elem_tree[i]<k && right!=0) ans+=right-left+1;

}

System.out.println(ans);

}

Алгоритм решения:
Зададим отрезок массива, на котором обозначим границы [latex]\left [ left, right \right ][/latex]. Инициализируем изначально оба конца нулем. Рассмотрим некоторое [latex]elem\_tree\left [ i \right ][/latex] на нашем сегменте. Тогда если [latex]elem\_tree\left [ i \right ]=k[/latex], то на всем отрезке от [latex]left[/latex] до [latex]i[/latex] максимумом будет [latex]k[/latex]. Увеличим в таком случае [latex]left[/latex] и сделаем его равным [latex]i[/latex], причем [latex]right=0.[/latex] Если [latex]elem\_tree\left [ i \right ]\lt k[/latex], максимум будет также равен [latex]k[/latex]. В таком случае увеличиваем только [latex]right.[/latex] Если же [latex]elem\_tree\left [ i \right ]\gt k[/latex] , то [latex]left[/latex] устанавливаем равным [latex]i+1[/latex], а [latex]right[/latex] обнуляем.
Пройдя по всему массиву, мы должны получить значения [latex]left[/latex] равное количеству пар в которых максимум равен [latex]k[/latex], а [latex]right[/latex] должно стать равным нулю.

Код программы на Java
Условие задачи