В рейтинге участвует:

групп:

каналов:

Виртуальный сервер на SSD - недорого!

Аренда выделенных и виртуальных серверов (VDS/VPS), хостинг, аренда IP-адресов, администрирование, круглосуточная поддержка

qwarta.ru подробнее

Резервное копирование с проверкой на вирусы!!!

Удобный сервис создания резервных копий на любой сервер сети интернет. Отслеживайте изменения, проверяйте на вирусы. Надежно защитите свой бизнес!

go.backupland.com

Выбираете сервер? Любая конфигурация на заказ!

Аренда физических серверов любых конфигураций под любые запросы - 1С бухгалтерия, игровые сервера, нагруженные проекты, интернет-магазины!

qwarta.ru подробнее

Size: a a a

pro.algorithms

1781 membersпожаловаться на группу
2020 November 03

AA

Adil Amirov in pro.algorithms
Всем привет. Задача: в массиве для каждого элемента a[i] нужно найти два других, которые стоят "правее" a[i] и при этом меньше, чем a[i]  (0 <= a[i] <= 10^9). Есть решение за квадрат. Вопрос: возможно ли это сделать быстрее?

input
7 2 5 3 1 2 1

output
7 2 5
2 1 1
5 3 1
3 1 1
1 - -
2 1 -
1 - -
источник
14:21пожаловаться#1

D

Dim in pro.algorithms
ты узбек?
источник
14:21пожаловаться#2

D

Dim in pro.algorithms
кто викард и оскам знает?
источник
14:23пожаловаться#3

EZ

Evgenii Zheltonozhsk... in pro.algorithms
Adil Amirov
Всем привет. Задача: в массиве для каждого элемента a[i] нужно найти два других, которые стоят "правее" a[i] и при этом меньше, чем a[i]  (0 <= a[i] <= 10^9). Есть решение за квадрат. Вопрос: возможно ли это сделать быстрее?

input
7 2 5 3 1 2 1

output
7 2 5
2 1 1
5 3 1
3 1 1
1 - -
2 1 -
1 - -
Произвольных?
источник
14:23пожаловаться#4

K

Kotomord_λapki in pro.algorithms
Расскажите человеку про декартово дерево
источник
14:24пожаловаться#5

AA

Adil Amirov in pro.algorithms
Evgenii Zheltonozhskii🇮🇱
Произвольных?
сорри, не уточнил. два "ближайших"
источник
14:24пожаловаться#6

K

Kotomord_λapki in pro.algorithms
Или про дерево отрезков
источник
14:25пожаловаться#7

A

Andrey in pro.algorithms
Kotomord_λapki
Или про дерево отрезков
Да, с ним проще обычно
источник
14:25пожаловаться#8

D

Dim in pro.algorithms
а это (0 <= a[i] <= 10^9) тут при чем?
источник
14:26пожаловаться#9

AA

Adil Amirov in pro.algorithms
ограничение на a[i]
источник
14:26пожаловаться#10

S

Stas in pro.algorithms
Kotomord_λapki
Или про дерево отрезков
Функция в дереве - храним максимальное значение на отрезке?
источник
14:27пожаловаться#11

A

Andrey in pro.algorithms
Stas
Функция в дереве - храним максимальное значение на отрезке?
Можно идти справа налево и хранить в ДО в позиции x самое левое вхождение x из уже рассмотренных
источник
14:28пожаловаться#12

EZ

Evgenii Zheltonozhsk... in pro.algorithms
Adil Amirov
сорри, не уточнил. два "ближайших"
Ну ближайший находится стеком за линию вроде
источник
14:28пожаловаться#13

A

Andrey in pro.algorithms
Andrey
Можно идти справа налево и хранить в ДО в позиции x самое левое вхождение x из уже рассмотренных
А второй ближайший можно найти вторым проходом
источник
14:28пожаловаться#14

A

Andrey in pro.algorithms
Ну либо персистентным ДО, если вы ценитель
источник
14:29пожаловаться#15

VS

Victor Shamparov in pro.algorithms
Dim
а это (0 <= a[i] <= 10^9) тут при чем?
Чтобы знать, что для хранения чисел достаточно int32
источник
14:29пожаловаться#16

D

Dim in pro.algorithms
на питоне это хорошо пишется
источник
14:30пожаловаться#17

AA

Adil Amirov in pro.algorithms
спасибо за мысли, буду думать дальше
источник
14:31пожаловаться#18

K

Kotomord_λapki in pro.algorithms
Stas
Функция в дереве - храним максимальное значение на отрезке?
Ага
источник
14:31пожаловаться#19

K

Kotomord_λapki in pro.algorithms
Andrey
Ну либо персистентным ДО, если вы ценитель
Почему? Просто реализуем функцию "найти минимальный элемент с индексом больше x и значением больше y
источник
14:32пожаловаться#20