тестовое задание для абитуры

Раскрашивание точек
ТL =1 секунда
МL=16 мегабайт
Лимит по памяти важен. Далеко не все интерпретируемые языки смогут запустить интерпретатор в этих ограничениях. Выбирайте инструмент в соответствии с задачей
Реализуйте структуру данных, которая может выполнять следующие две операции:
PAINT(х, у, со1) -- покрасить точку (х, у) в цвет соl
QUERY(х, у) — определить цвет точки (х, у).
Покрашенные точки могут быть красными или синими.
Изначально все точки плоскости считаются непокрашенными.
*Известно, что размер любого множества точек, в котором совпадают остатки от деления координат х на 100019, не превосходит 100.

Поясните что им *ИЗВЕСТНО ?
последнее предложение вызывает затруднение понимания.

Ощущение корявого перевода вырванных из контекста предложений

Обрати внимание что область координаты Х не задана.
Условие, которое ты спрашиваешь, говорит о том, что разброс точек по Х не должен превышать 100019*100
Фактически крайняя левая точка если имеет координату Хmin то крайняя правая - Хмах = Хmin+100019*100-1

вдогонку к (2) И даже больше того, это при условии константной Y. Так же можем сказать, что больше чем 100 по оси Y быть не может.

(3) стало еще меньше понятно

они намекают на размерность матрицы?

Понятно что намекают на необходимость произвести контроль исходных данных типа
if (x%100019)<=100 then good else alarm

т.е. тестируют на внимательность при чтени условий задачи?

(6) размер группы, а не Х. Х, У могут быть сколь угодно большими, но всего в множестве не больше 100019*100 точек.

размер группы у которых координаты: x, x+100019, x+2*100019, ...
не более 100

очевидно таких групп не более 100019

(0) если бы это было задание для языка низкого уровня(а то и машкода), то я бы сказал, что это условие нужно для организации разметки видеопамяти(ограничение размера блоков и общего количества)

а координата У любая ?
В чем смысл этого уточния задания?

В решении что нужно предусмотреть?

Или как вариант, если для хранения множества всех точек(для ускорения определения цвета, например) используется структура данных, то размер каждого элемента - не превышает 100, т.е. хватит 1 байта.

В задании РЕАЛИЗОВАТЬ СТРУКТУРУ ДАННЫХ
т.е. не написать программу, нарисовать ТЗ на структуру хранения данных для указанной задачи.
Т.е., например МАССИВ струтур
где элемент структура типа:
struct screen {
byte x, y;
char colour;
};

и на этом все?

(13)"Реализуйте структуру данных, которая может выполнять следующие две операции"

т.е. не просто структуру, а структуру и два метода к ней

(0) Это значит что зазмер Х * Y не превышает 100019 * 100
Но не обязательно что размер Х = 100019, а Y = 100, возможны любые комбинации, например размер X = 1000190, Y = 10.
Главное чтобы произведение макс.Х * макс.Y было меньше 100019 * 100

Короче задача не для тупых которые не могут понять даже условие.

И Y не может быть больше 100, тоже из этого же условия.

По русски, размер множества не превышает 100, при условии.
А вот условие ))) не по русски.

(15) А кто сказал, что множество точек - прямоугольное?

(0)ИМХО. Задача поставлена не корректно.
"...Реализуйте структуру данных, которая может выполнять следующие две операции..." Структура данных не может выполнять операции.
По последнему предложению, поддержу (7)

(13) не удобно будет искать цвет точки
нужно чтоб х, у были индексами

(21) это если задать матрицу размерность  охулион на охулион, тогда индексы.
А если линейный массив размерностью N - то ….

(20) Структура данных может выполнять операции. Так как в ЯП у структур есть методы.

(20)т.е. по (7) уже можно сказать про размерность массива?

+ (23) Структура данных (англ. data structure) — программная единица, позволяющая хранить и ОБРАБАТЫВАТЬ множество однотипных и/или логически связанных данных в вычислительной технике. Для добавления, поиска, изменения и удаления данных структура данных предоставляет некоторый НАБОР ФУНКЦИЙ, составляющих её интерфейс.
https://ru.wikipedia.org/wiki/Структура_данных
Ключевые слова выделил капсом.

На 1с  - это типо
Соотвествие[x + '_' + y] = Цвет

(15) > Это значит что зазмер Х * Y не превышает 100019 * 100

Это откуда? В (0) ни слова про ограничения на Y.

Общий смысл ограничения понятен. Есть лимит по памяти, и если хранить тупо в массиве или списке, то все точки туда не влезут. А нужно придумать что-то хитрее, чтобы влезли.
Но вот детали пока ясны...

(27) *пока не ясны*

(26) ну или бинарное дерево (индекс по 2м полям)

(27) Ограничения не на количество значений координаты Х, а на общее количество точек!

там дальше в задании

В первой строке входных данных содержится число запросов п (1 < п < 105).
В каждой из следующих п строк содержатся запросы. Запросы выполняются в том порядке, в котором они встречаются во входных данных. Разные запросы могут односиться к одной и той же точке (в частности, некоторые точки могут быть перекрашенными в процессе, см. пример).

т.е. N меньше 10 в пятой степени

(26) И вывалишься за ограничение.
10 миллионов значений, на каждое пара байт - это 20 мегабайт.

т.е. это кол-во запросов , которые есть или установить цвет точки или получить цвет точки. значить матрица можетбыть не более 100000 элементов

(31) Если запросов 10^5, то можно делать операции добавления и удаления за lnN, уложишься в таймлимит.
Ну и вообще в условии должны быть ограничения на x и у.

Поясняю: дана двумерная система координат. Кусок плоскости пикселей, в любом месте которого пиксель имеет координату Х и У.
Этот кусок плоскости должен быть таким (такой формы), что в нем будет не более ста пикселей, координата Х которых кратна 100019.
Т.е. это может быть:
- вертикальный столбик из ста пикселей: каждый пиксель будет иметь одинаковую координату Х, но разную координату У
- горизонтальный отрезок из 100019*100 пикселей и высоток один пиксель: у всех одинаковая координата У, и в нем будет сто пикселей, координата Х которых кратна тому числу 100019
- любой прямоугольный (?) участок между этими двумя "крайними формами"

есть только на х

(31) Полностью задание можешь выложить?

(33) так не нужно же все хранить, только те что перекрасили

(37) Какое? Если х и y неограниченные, то на хранение координат одной точки может уйти больше 16 мегабайт.

Область вариантов скорее всего выглядит как экспонента.
Т.к. если после вертикального отрезка (высота 100 пикселей, ширина 1) увеличивать ширину, то высота сразу уменьшается пропорционально увеличению ширины

(39) При любых начальных условиях, укладывающихся в ограничения, программа должна тратить не меньше 16 мегабайт памяти указанных в условии. Это основное условие всех подобных задач.

Я привел вариант при котором 16 мегабайт не хватит.

эхх, далек я от олимпиадного программирования

(38) http://prntscr.com/kgyyos

Там же написано - 0<=x,y<=10^9

Теперь, учитывая что запросов не больше чем 10^5, то и покрашенных точек не больше этого количества.
Оптимально - использование HashMap.

(46) точно, еще хуже.

100 000 запросов на покраску точек, для каждого нужно сохранить еще 2 числа не более чем 1 000 000 000 и цвет R или B.

(49)+ 400 килобайт хватит на все

(50)+ сорри ошибся надо 800 килобайт

Понятно что по памяти легко укладывается, и по производительности (С любой структурой с скоростью доступа не хуже lnN)
(50) Число до 10^9 это уже 4 байта,
две координаты это 8 байт, и один байт на хранение цвета (вообще бит, но пусть будет байт - проще организовать).
Итого 9 байт на точку, 100000 точек. Это 900000 кбайт.
Но и HashMap и Map тратят еще память на вспомогательные данные, но в 16 МБайт конечно в любом случае укладываешься.

(52) >Число до 10^9 это уже 4 байта,

неа 2^30 же хватит и еще аж 4 бита останутся для цвета с двух чисел

(52) Нахрена HashMap или Map когда обычного линейного массива хватит?

Какая разница что для определения текущего цвета точки будет цикл по 100 000 элементам массива?

(54) а ты успеешь за 1с покрасить 100тыщ точек?

(55) Не покрасить а выполнить 100 000 запросов каждый из которых или на покраску или определение цвета

(56) ну ты же не знаешь сколько и каких запросов

(56)+ Это сильно зависит от тактовой частоты и накладных расходов на выполнение в реальной системе.

(55) Успею. Частота проца такая, какую я захочу:)

(58) но тем не менее, если не уложишься то твое решение не примут

(57) Там сказано ограничение на n (число запросов указанное в первой строке входных данных) 1<=n<=10^5

Самая хреновая ситуация если все 100 000 запросов на определение цвета, будет 100 000 циклов по 100 000 строк массива.

Надо бы отдельно сохранить число выполненных запросов на покраску и цикл только по ним делать при определении цвета.

(62) а для покраски разве не нужно по массиву бежить? перекраска же возможна

(63) Хехе не надо, при покраске просто в конец массива дописываем x,y,col

(64)+ При определении цвета пробегаемся по всему массиву, если координаты встретили то запоминаем цвет, повторно встретили поменяли, если ни разу то цвет N

(64) тогда для поиска тебе нужно будет каждый раз бежать до конца массива

"Изначально все точки плоскости считаются непокрашенными. "
Красные в массив х, синие - в y. Оставшиеся - в z. Всегда первыми проверяем самые короткие. Если в первых двух нет - точка в третьем.

(66) Не до конца массива а до кол-ва выполненных (записанных) запросов на покраску

(67) Угу ускорение за счет большего выделения и использования памяти, у нас аж 16 мегабайт еще можно развернуться

(69)+ Намек как делить массивы дан:

"*Известно, что размер любого множества точек, в котором совпадают остатки от деления координат х на 100019, не превосходит 100"

(70)+ Как понимаем поделить координату x на 1000019 и сравнить остаток это быстро

(54) С обычным массивом ты не укладываешься в таймлимит.
Потому что сложность алгоритма О(N^2) при N=10^5 это 10^10 операций, а успеть за секунду можно 10^7

(58) Могу еще раз посоветовать немного порешать задач на codeforces. Будешь лучше ориентироваться в сложности.
Твое решение с поиском каждый раз по массиву не укладывается по времени в 1000 раз.

(72) С одним возможно но массивов 100 и мы ищем цвет точки только в 1

(71) Еще раз повторюсь, можно успеть за секунду сделать 10^7 простейших операций. Если в условии 10^5 запросов, то сложность алгоритма должна быть не хуже NlnN

(75) >за секунду сделать 10^7 простейших операций

Это уже зависит от частоты процессора

(76)+ И да 10^5 меньше чем 100^7

(77) *10^5 меньше чем 10^7

Данные массива:
(КоординатаИгрек, КоординатаИкс, смещение, Цвет)
Смещение - количество точек одного цвета

(74) Ты пытаешься изобрести велосипед. Это совершенно шаблонная задача.
(76) Это простейшая задача спортивного программирования. Я кандидат в мастера (КМС) codeforces (До девальвации рейтингов был КМС-ом), ты ни разу не участвовал в спортивном программировании. Зачем ты споришь?

+(79) Если один массив

(80) в чем состоит шаблон этого типа задач?

(78) Тебе 10^5 раз нужно сделать операцию поиска точки в массиве. Посчитай сколько всего операций тебе нужно сделать.

(82) Это задача добавления и чтения значений. Обычная несложная стандартная задача. Решаемая при помощи HashMap.

(83) Сделать максимум 10^5 раз в одном из 100 массивов по 1000 максимум элементов.
Еще расходы на операции по определению в каком из массивов искать.

И да ты думаешь внутри HashMap что то отличающееся от обычных массивов?
Там просто добавлены накладные расходы на перебор массива ссылок при добавлении записей, перебор всех записей (таблицы адресов) при получении значений никуда не девается ))

(85) 10^5 раз просмотреть все элементы массива из 1000 значений. Это 10^5*1000 операций. 10^8. Вопрос - ты издеваешься? Говорю еще раз, стандарт спортивного программирования - 10^7 операций таймлимита.

(85) Поиск в обычном массиве из 1000 элементов это 1000 операций, в HashMap - это одна операций. Я не думаю, я знаю.

(87) Хера се... Это какая то новая арифметика каких то квантовых процессоров?

В бинарном дереве это 10 операций (Map). В хеше одна операция. Уже вторая ветка подряд где ты советуешь пургу, при этом и в первый раз не понял что дождаться ответа твоего решения невозможно. Потому что и там был N^2.

(88) Блин. Ты что такое бинарное дерево знаешь? Понимаешь что в бинарном дереве поиск это десять операций?
https://ru.wikipedia.org/wiki/Хеш-таблица
Вот описание Хеш таблицы. Исходя из хеша вычисляется адрес (одна операция), и по этому адресу лежит значение. Это в двух словах устройство хеш-таблицы.
Если не понимаешь принцип жействия Хеш-таблиц, то можешь использовать бинарное дерево, в котором поиск не за Nопераций, а за Ln N - это "Map".
Решение на Map тоже укладывается в лимит.

(89) http://korzh.net/wp-content/uploads/2010/11/image008.gif - четкая зависимость кол-ва операция от количества объектов внутри - перебор же ))

В задаче не сказано что можно использовать готовый HashMap.

Ты предлагаешь его реализовать вручную? На чем? На массивах?

Вперед и заодно покажешь что не гонишь пургу.

(90) В бинарном дереве поиск это не 10 операций а зависит от его размера

(92) Это 10 операция для 1000 элементов! Жесть просто. Я  тебе же пишу что это О(lnN), ты понимаешь что N - это и есть размер массива?

(93) Ты только что выше писал "в HashMap - это одна операций. Я не думаю, я знаю." соврал?

(94) Ты понимаешь что HashMap это не бинарное дерево, в нем не О(LnN), а О(1)?

По сути я как раз и предлагаю реализовать хеш-таблицу вручную, разбив данные по нескольким массивам, не хватает 100 массивов? Сделаем 1000 или 10 000

https://habr.com/post/128017/

(97) Прикинь я это читал. И даже понимаю что мое предложение это и есть хеш-таблица, точнее некая реализация нечто похожего.

(96) Ты изобретаешь велосипед. HashMap, Map - Это готовые структуры, которые нужно уметь использовать в спортивном программировании. А в (0) как раз задача спортивного программирования.
Еще раз Map - бинарное дерево, операции добавления, поиска выполняются за О(LnN). HashMap - хеш-таблица, операции жбавления и поиска выполняются за О(1)

"МL=16 мегабайт
Лимит по памяти важен. Далеко не все интерпретируемые языки смогут запустить интерпретатор в этих ограничениях. Выбирайте инструмент в соответствии с задачей"

Покажи мне интерпретатор имеющий на борту HashMap и работающий в этих ограничениях в 16 Mb RAM ?

(100) Это обычная фраза задач спортивного программирования.
Когда ты отсылаешь решения, сервер контролирует сколько памяти ты используешь.
https://codeforces.com/problemset
Не поленись, открой любую задачу.
Обязательные атрибуты задачи
//
ограничение по времени на тест:
ограничение по памяти на тест:

Это не ответ - это посылание на некий сайт не имеющий никакого прямого отношения к задаче из (0)

>Ты изобретаешь велосипед. HashMap, Map - Это готовые структуры, которые нужно уметь использовать в спортивном программировании.

Твоя позиция очень похожа на:

Нет готового "HashMap"?
Это не моя проблема я участвую только в "спортивном программировании"

(103) Я умею реализовать и HashMap и Map.

(104) Так блин дана готовая хеш-функция

"Известно, что размер любого множества точек, в котором совпадают остатки от деления координат х на 100019, не превосходит 100"

(102) Еще раз - это задача спортивного программирования, поэтому там указан лимит по памяти и по времени. Не более того.
Я тебя отсылаю на сайт, потому что походу ты из лимита по памяти построил странную теорию, из которой следует что нельзя использовать HashMap. А я тебе говорю что это обычное условие задач спортивного программирования. И никакого отношения к запрету HashMap или использованию неких слабых и старых интерпретаторов или компиляторов оно не имеет.

(105)+ Эээ гм не 100 массивов а хз скоко массивов из максимум 100 элементов

В принципе не принято в спортивном (и не только) программировании решать за О(N^2) задачи которые решаются за О(NlnN). Если это задача на собеседовании - то тебя просто не возьмут на работу.

(108) 10^5 * 100 = ?
укладываемся же!

(107) Задача в (0) появилась ведь не просто так? А служит для проверки понимания что такое сложность алгоритма. В принципе все задачи спортивного программирования именно это в том числе и проверяют. Ты своим решением хочешь показать что? Что ты не знаешь как эту задачу можно решить за NlnN, а умеешь только за N^2?
Когда будет 10^7 запросов, ты полностью перепишешь решение, чтоб уложиться в 50 секунд?

(110) Хочешь сказать что это строчка про "...не превосходит 100" в задаче лишняя?
И не подразумевает использование этих знаний например для ручного хеширования?

(111) Лишняя. Считай что она нужна только для того чтоб запутать.
Кстати, то что ты предлагаешь, разделение массива на множество поменьше - это ну никак не Hash таблица, а больше похоже на  sqrt-декомпозицию.

(112) "sqrt-декомпозиция" - тут и близко не стояла это из какой то совсем другой оперы

Это условие добавляет  возможность сделать более простое но и более плохое решение. Бывает такое что задача имеет несколько решений, и в зависимости от качества (память, сложность, скорость) решения дается разное количество баллов.

(113)+ Точнее общее только разбиение (но при хеш-функциях это же и происходит) на примерно равные множества, но никаких сумм не надо считать

(113) sqrt-декомпозиция, это когда для того чтоб быстрее искать, мы по некоторому признаку массив из N элементов делим на много массивов. Примерно Корень из N массивов по корень из N элементов.
А Хеш таблица классическая работает на списках, а не как массив массивов.

(115) Только что, в (87), ты говорил что не существует структуры с поиском за константное время, а теперь уже стал знатоком хеш-таблиц? :)

(117) любая хеш таблица реализована или на массивах или на списках
Список это частный случай массива когда колво элементов заранее неизвестно

В данной задаче макс колво известно отсюда какой вывод?

(118)+ решать задачу через массивы возможно оптимальнее пусть и сложнее но работать будет быстрее и точнее лимиты на память

(117) обход списка затратнее чем обход массива

(120) Хеш таблицы не делаются на массивах (точнее делаются, но только когда нам не обязательно избегать коллизий), потому что тогда по каждому адресу тебе нужно держать массив размером на максимальную длину цепочки, на это никакой памяти не хватит.

(121) Если известна максимальная длина цепочки как в данной задаче то?

(119) Очередная жесть. Решение за (О(N^2)) оптимальнее чем  О(nLnN)? Потому что всегда будет медленней?
Ты разберись со сложностью алгоритма. Что это такое. Решение на HashMap - это решение за О(N). 10^5 операций.
Решение на Map - это решение за 2*10^6 операций.
А твое решение мало того что  медленнее, еще и не рабочее.

(123) Зачем перебирать каждый массив до конца?
Когда можно хранить кол-во заполненных элементов в каждом и цикл только до него.

Судя по чисто нашему диалогу (без участия других) остальные или уже нифига не понимают или им неинтересно ))

(122) Сколько ты собираешься завести массивов из 100 элементов? 10^5? Опиши еще раз структуру (массивы) которая будет работать не за 10^10 операций, и влезет в память по условию.
(124) Ты точно знаешь что такое сложность алгоритма?

(125) Судя по нашему диалогу - ты ничего не понимаешь. :)

(126) Завести собираюсь ровно 1000 массивов по 100 элементов

(127) Блин я прекрасно понимаю твое решение и свое решение. Ты понимаешь только свое. И?

(128)+ Еще 1000 целых чисел - кол-во заполненных элементов в каждом из 1000 массивов

(130)+ Естественно в отдельном массиве из 1000 элементов а не 1000 переменных ))

(128) И по какому признаку ты будешь решать в какой из 100 массивов писать свою пару координат?

(132) "совпадают остатки от деления координат х на 100019"

(132) Из 1000 массивов

(133) (134)
Еще раз.
Вот у тебя x и y
Напиши функцию от x и y - которая возвращает число в интервале от 1 до 1000, массив в который ты будешь писать значение цвета по этой координате.
В (133) Ты написал строчку из условия, а не описал свой алгоритм.

(133) У всех 10^5 пар допустим разные остатки от деления. От 1 до 100000.

Пары точек x,y
1,1
2,2
и т.д. до
10^5, 10^5
В какой массив попадет каждая из точек?

Ты наверно хочешь сказать что ты сделаешь 100019 массивов по 100 значений. Но тогда ты не влезаешь по памяти.

(137) Об этом я еще не подумал, хз как доказать что будет всего 1000 массивов и/или какую еще хеш-функцию придумать чтоб объединить массивы <100 элементов

когда x от 1 до 1000000000

(137) точек всего 10^5 так что 19 массивов точно лишние

(139) И как ты до того как получил значение этих 10^5 точек узнаешь какие из массивов лишние? Ты же вроде хочешь сразу объявить двумерный массив. Или это какие-то хитрые массивы, которым можно присваивать индекс в потоке?

Я так понял, что ты теперь понимаешь что твое решение не укладывается по памяти?

(140) Одного массива 10^5*100 разве не хватит?

(142)+ Двумерный массив 100000 на 100

(143) И какие у тебя будут исключены остатки по модулю 100019 при заведении массива?

Вот у тебя в потоке первая точка
1,100
Вторая 100019,100
//
В какой элемент массива ты запишешь первую, в какой вторую?
//
10^5*100*8 байт (две координаты, х и y, каждая по 4 байта) это 80 мегабайт.

(144) Входной поток он линейный с последовательным чтением или можно возвращаться к старым элементам но номеру?

(145) Допустим можно возвращаться.

(23) Спасибо за поправку. Век живи, век учись.

Ну вы монстры... Дочитал до сюда. Вроде понимаю о чем говорите, но блин так это далеко и давно было. И "по кусочкам"...
Вот ТС куда-то слился.

(144) Хм делаем массив 100019 х 100 и x координата задается остатком от деления, внутри храним в 100 элементах только y координату

(148)+ не влазит 40 мегабайт будет ((

(148) И как ты отличишь две разные точки, с разным x, но с одинаковым остатком от деления на 100019?

(149)+ Но если можно возвращаться (146) то хранить можно не значение y координаты а номер точки из входных данных

(150) Они рядом будут записаны в 100, их порядковым номером (151)

(151) Как, ииз какой структуры ты будешь получать номер точки?
Вот у тебя пара запросов на изменение цвкта точки, и один чтение. Тебе каждый раз после первой записи нужно точно определить "порядковый номер точки". Как ты это сделаешь? Хеш-таблицей? Map? :)

+ (153) Три раза встретилась одна и та-же точка, как ты узнаешь что это одна и та-же точка, если ты не хранишь её координату?

(154) Чем то напоминает задачку на сжатие данных, координаты у нас до 10^9 но точек всего 10^5 можно составить "словарик допустимых координат"

Ответ же нам нужен только цвет R, B или N координату не надо возвращать - их можно не хранить.

Провести при чтении некую замену координат где будет подмена порядкового номера точки встретившегося позднее на самый первый номер этой же точки (с этими же координатами).

"координаты у нас до 10^9" // Орицательные тоже могут быть. Т.е. координата по У ограничена только сверху, а по Х - только слева (больше нуля, типа). Плюс есть ограничение на размер области по высоте и ширине, описанные мною ранее

(156) 0 <= x,y <= 10^9
https://prnt.sc/kgyyos

И Я про то же. Не ясно, зачем ты это написал.

(158) Не может быть отрицательных координат x или y

(155) Ты понимаешь что элементарную задачу, которая решается начинающим программистом, джуниором - минут за 5 - ты превратил невесть в что, и до сих пор не выдал рабочего решения укладывающегося в лимиты?
Когда есть решение в ветке за О(N), на hashMap, и понятно что при N элементах в потоке - решения с лучшей асимптотикой быть не может. Так как на чтение из потока нужно О(N) операций.
(156) В условии написано: 0<=x,y<=10^9
Эта запись означает что обе координаты меньше либо равны 10^9, и обе больше либо равны нулю.

(159) (160) Это одна из двух возможных трактовок

(160) Для решения на hashMap, ты ключом что будешь делать?

Сколько будет операций при добавлении новых значений в 10^5 HashMap или получении значения оттуда?
Число 10 операций откуда взялось?

(162) 10 это двоичный логарифм от 1000. К hashmap это не имеет никакого значения. Это количество операций для поиска и добавления значения в "map" (бинарное дерево) с 1000 элементами.
//
В HashMap добавление и чтение это О(1) - константа. Одна операция.
Для добавления 10^5 значений в HashMap потребуется 10^5 (О(10^5)) операций.

(162)+ Ключ (x+y) записываем в 8 байт, еще 1 байт для цвета.
Макс элементов 10^5 итого 10^5 * 9 = 900 килобайт.

Но не учитываются накладные расходы на хранение списка ключей и списка значений, а они для 10^5 элементов будут немаленькие.
https://habr.com/post/159557/

(163) >В HashMap добавление и чтение это О(1) - константа. Одна операция.

Офигеть а за сколько времени выполняется эта одна операция в мс?

(165) Я выше приводил картинку где есть размеры коллекций и быстродействие

(166)+ http://korzh.net/2010-11-proizvoditelnost-osnovnyx-kollekcij-java-sravnenie-s-analogami-net.html

(165) Неважно. Там константа конечно больше чем в map, но не на много.
Около 10^-6 сек.
(166) И что ты понял из этой картинки? Что реализация HashMap не очень хорошая, и сложность конечно заметно меньше логарифма, но чуть хуже чем О(1)?
А хорошая реализация в LinkedHash?
Ну и что?

До 50000 элементов , а это и есть почти 10^5, как и есть в условии - скорость доступа 1микросекунда, 10^-6. Зависимость становится чуть хуже чем константа на намного больших размерах.

(164) Немаленькие это в 20 раз больше, или максимум в два раза больше? По условию у нас лимит до 15 мегабайт.
(162) Это очень странный вопрос. Конечно
typedef pair<uint, uint> Key;

Всё было описано выше. На хранение каждой точки нужно 9 байт. Итого потребуется 900 килобайт, ну и естественно плюс накладные расходы. Допустим даже в 10 раз больше. Все-равно укладываемся.
Не укладываешься - так поменяй в коде hashmap на map, делов то. Будет чуть медленней, на логарифм, но места будет занимать меньше.

(171) Угу 3 мегабайта накладных расходов примерно

(147)  +1
Почитал, как будто снова окунулся в детство.  Все это было, но блин так давно. Чувствую уже давно стал "не программистом",  совсем мозг заплыл адинэсом. )

#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
typedef pair<unsigned int, unsigned int> Key;
struct pair_hash {
    template <class T1, class T2>
    std::size_t operator () (const pair<T1,T2> &p) const {
        auto h1 = hash<T1>{}(p.first);
        auto h2 = hash<T2>{}(p.second);
        return h1 ^ h2;  
    }
};
int main()
{
    std::ios::sync_with_stdio(false);
    unordered_map <Key,char,pair_hash> a;
    int n;
    int op;
    unsigned int x,y;
    char c;
    cin >> n;
    for(int i=0;i<n;i++) {
      cin >> op >> x >> y;
      if (op==1) { cin >> c; a[make_pair(x,y)]=c;} else
      {
      auto f=a.find(make_pair(x,y));      
      if (f==a.end()) cout << 'N'; else
        cout << f->second << "\n";
      }
    }
    cout.flush();
    return 0;
}
Вот код,
если не нравятся Хеш-таблицы, достаточно unordered_map поменять на map

виноват, косяк, забыл перевод строки, в тестовом примере ‘N’ в последней строке, поэтому глюк не заметил
auto f=a.find(make_pair(x,y));      
      if (f==a.end()) cout << 'N' << "\n"; else
        cout << f->second << "\n";

это на каком ЯП??

(176) C++
можешь проверить на любом онлайн компиляторе. Я так и проверял на тех входных данных которые на твоем скриншоте задания.
могу написать на другом ЯП. На каком надо?

(177) На 1С давай, чтоб всем понятно было )

(178) на 1с слишком просто.
только условие не выполнить, 1с не умеет читать из консольного ввода.

(176) Извиняюсь, а точно имеет смысл абитура?
Конечно ИМХО, но С++ хорошо бы знать в лицо.
Очень рекомендую.

(177) на с

(177) и еще …
в задании указаны условия, нужно ли в решения делать проверку условий или условия указаны для понимания объема данных и ресурсов

(182) нет, проверку делать не надо. все условия написаны для того чтоб понимать что может быть во входном потоке.

код на C++11, он немного ускоряет написание по сравнению с чистым C++

нужен чистый классический С

(179) 1с умеет же читать с консоли
ВвестиЧисло

(185) это не то :)
вечером, освобожусь, напишу на си
задачу можно решить без использования индексов, бинарных деревьев и хеша, на списках.
заводим массив на 100019 элементов, в который пишем ссылку  в списке на первую точку с заданным остатком от деления x на 100019.
а в списке (общем для всех точек) с каждой точкой хранится ссылка на следующую точку с таким же остатком от деления.
итого у нас на поиск каждой точки уйдет не больше 100 операций.
И в лимит по памяти легко уложились.

т.е. мы вычислили что объем массива не более 100019 ?

я не понял в чем фишка остатка от деления. что это определяет?

(187) В условии написано что таких чисел не больше ста.
У нас есть точка с координатой x,y
Если мы будем искать её в нашей структуре только среди точке с остатком отделения x на 100019 таким-же как и у текущей точки, то потратим на это не более 100 операций, потребуется перебрать не больше 100 точке.

Структуры для хранения две.
Первая - массив на 100019 элементов, по два байта на значение - ссылка на первый элемент с заданным остаток от деления в списке.
Вторая - связный список, на N+1 элементов
(максимум на 100001). Для удобства нулевой элемент использовать не будем, 0 - это будет пустая ссылка.
В котором хранятся координаты x и y (8 байт), цвет (1 байт), и ссылка на следующий номер элемента в этом массиве с таким-же остатком от деления x на 1000019 (2 байта)
Итого 100001*11+100019*2 байт, чуть больше мегабайта.
Связный список сделаем на массиве - для скорости. Чтоб не выделять память по одному элементу.

+(189) То есть мы по сути реализуем хеш-таблицу, где в качестве хеша используется остаток от деления координаты x на 100019. Как и хотел Garykom, но у него что-то не получилось :)

Виноват, все ссылки по 4 байта.

#define size 100019
#define maxN 100001
#include <stdio.h>
#include <stdlib.h>
typedef unsigned long int UINT;
typedef struct node
{
    UINT x,y,next;
    char c;
};
struct node List[maxN];
UINT Hash[size];
UINT ListN=0;
char QUERY(UINT x, UINT y)
{
    UINT p=Hash[x%size];
    while (p!=0)
    {
        struct node Node=List[p];
        if ((Node.x==x)&&(Node.y==y)) return Node.c;
        p=Node.next;
    }
    return 'N';
}

void PAINT(UINT x, UINT y, char col)
{
    UINT p=Hash[x%size];
    while (p!=0)
    {
        if ((List[p].x==x)&&(List[p].y==y))
        {
            List[p].c=col;
            return;
        }
        p=List[p].next;
    }
    List[++ListN].x=x;
    List[ListN].y=y;
    List[ListN].c=col;
    List[ListN].next=Hash[x%size];
    Hash[x%size]=ListN;
}
int main()
{
    int i;
    for (i=0; i<size; i++) Hash[i]=0;
    int n;
    scanf("%d",&n);
    UINT op,x,y;
    char c;
    for (i=0; i<n; i++)
    {
        scanf("%lu%lu%lu",&op,&x,&y);
        if (op==1)
        {
            do
            {
                scanf("%c",&c);
            }
            while ((c!='R')&&(c!='B'));
            PAINT(x,y,c);
        }
        else
            printf("%c\n",QUERY(x,y));
    }
    return 0;
}

#define size 100019
#define maxN 100001
#include <stdio.h>
#include <stdlib.h>
typedef unsigned long int UINT;
typedef struct node
{
    UINT x,y,next;
    char c;
};
struct node List[maxN];
UINT Hash[size];
UINT ListN=0;
char QUERY(UINT x, UINT y)
{
    UINT p=Hash[x%size];
    while (p!=0)
    {
        if ((List[p].x==x)&&(List[p].y==y)) return List[p].c;
        p=List[p].next;
    }
    return 'N';
}

void PAINT(UINT x, UINT y, char col)
{
    UINT p=Hash[x%size];
    while (p!=0)
    {
        if ((List[p].x==x)&&(List[p].y==y))
        {
            List[p].c=col;
            return;
        }
        p=List[p].next;
    }
    List[++ListN].x=x;
    List[ListN].y=y;
    List[ListN].c=col;
    List[ListN].next=Hash[x%size];
    Hash[x%size]=ListN;
}
int main()
{
    int i;
    for (i=0; i<size; i++) Hash[i]=0;
    int n;
    scanf("%d",&n);
    UINT op,x,y;
    char c;
    for (i=0; i<n; i++)
    {
        scanf("%lu%lu%lu",&op,&x,&y);
        if (op==1)
        {
            do
            {
                scanf("%c",&c);
            }
            while ((c!='R')&&(c!='B'));
            PAINT(x,y,c);
        }
        else
            printf("%c\n",QUERY(x,y));
    }
    return 0;
}

Так единообразней. По сути это реализация простейшей Хеш-таблицы.

В typedef struct node - typedef лишнее. Нужно писать
typedef unsigned long int UINT;
struct node
{
    UINT x,y,next;
    char c;
};
struct node List[maxN];

ТС ты не одинок, но я не поступаю :)
"Известно, что размер любого множества точек, в котором совпадают остатки от деления координат х на 100019, не превосходит 100"

...множество(из пар х и у), в котором совпадают остатки от деления координат х на const = 100019 (x1/const=xN/const). Или  хто там должЁн совпасть?

NSSerg слился, ...

Да и фиг с ней.

(196) в смысле?

(198) из ветки. Понятно, что мастера тупняки достали.

(177) на вход подаются в том числе запросы на добавление точек, с координатами (x,y)
И разных точек, но при этом с одинаковым x%100019  - не может быть больше ста.

а вы видели пример входящих данных? там х далеко не 100019

(201) Это к чему?

(201) Если вам там учиться, и уже сейчас дают задачи уровня "В"-"C", то такие задачи в любом случае придется учиться решать.
Чтоб не было непоняток с условиями, не было далеко идущих выводов из тестовых примеров, нужно просто зарегистрироваться на codeforces.ru и начать решать задачи, например начиная с тех, которые решило большее количество участников.
https://codeforces.com/problemset?order=BY_SOLVED_DESC
Практически сразу станет проще ориентироваться в подобного рода заданиях.
Значение имеют только условия. Тестовый пример в условии всегда простой, и не покрывает всех возможных случаев. Только даже если бы в примере было x=100019 - что это меняет? Условие то осталось прежним.

(200) С делением по модулю и совпадениями понял, хоть это было и не мне. Это как-то влияет на множество точек плоскости для раскраски?

(204) Если мы формируем списки по точкам с заданным x%100019, то мы можем быть уверенны что влезем в TL.
Каждую точку мы ищем пробегаясь по списку из уже добавленных точек с фиксированным x%100019, а список не более чем из 100 точек по условию. Всего запросов максимально 10^5 из условия. Всего максимальное количество операций получается равно количество запросов помноженное на максимальное количество операций в каждом запросе, это 100 операций.
Итого 10^5*100=10^7 операций. Точно уложимся.

(204) Это не деление по модулю, это остаток от деления.

(206) Хотя ладно, это почти одно и то же :)

Что-то не увидел в условии, что нет множеств точек, в которых не совпадают остатки от деления координат х на 100019

(0) Что есть абитура?

(208) "Известно, что размер любого множества точек, в котором совпадают остатки от деления координат х на 100019, не превосходит 100."
Код в (193), при каждом запросе - ищет только среди точек с совпадающим x%100019 с искомой точкой. А по условию таких точек не больше 100. Если бы их было не больше 10000, то при некоторых наборах исходных данных код бы не укладывался в таймлимит. Но их не больше 100, и это дает возможность использовать x%100019 как значение хеш функции, и гарантирует что цепочка значений не будет превышать 100 элементов.

(205) В условии вроде бы про размер интерпретатора?

(211) В условии, как и в любой другой задаче спортивного программирования - про ограничения на время, и на память.

TL - таймлимит.
ML - меморилимит.
Накладывает ограничения на алгоритмы, чтоб не прошли медленные и требующие большого количества памяти решения.
Данное ограничение отсекает все решения за О(N^2), и простые решения требующие огромного числа памяти.

(212 Лимит по памяти важен. Далеко не все интерпретируемые языки смогут запустить интерпретатор в этих ограничениях. Выбирайте инструмент в соответствии с задачей. Это разве о данных? Как вы time вычисляете?

СПС

(214) Есть общепринятые стандарты количества простых операций которые можно выполнить в одну секунду. Это порядка 10^7, максимум 5*10^8
Чтоб его прочувствовать самостоятельно, достаточно (203)
Как и везде там автоматическая проверка, и выводит и время вычисления, и израсходованную память, и TL или ML если превысил. То есть любой человек с достаточным опытом решения задач спортивного программирования - понимает сколько операций влезет в TL.
А чтоб проверить память - достаточно sizeof, посмотреть в диспетчере задач, либо просто уметь её вычислять.

Яндекс проводит чемпионат  по программированию
В этой ветке немного есть про термины и суть подобных задач.

Короче делаем так.

1. Берем пример одного прекрасного узкоспециализированного решения.

2. Формулируем его в задачу.

3. Т.к. без трудностей с которым пришлось столкнутся гению из (1) задача решается на раз-два, дополняем её тупыми условиями.

4. Готово! Можно запускать.

Такая херня через раз встречается на собеседованиях. Особенно если вас собеседует тот самый гений из (1). А задача - говно.

(218) Если ты хочешь стать алгоритмистом-программистом, то должен уметь пользоваться инструментами для проверки качества решения, и уметь решать типовые задачи. Любой студент современный на прикладной математике и информатике и подобных специальностях - должен щелкать такие задачи как орешки, учитывая что она в лоб на map или hashmap решается за несколько минут.
Подобные задачи решают  и в вузах, и на собеседованиях на должности где требуется алгоритмика в любой серьезной компании. Ну и что-то мне подсказывает что они знают как выявлять способности и познания в алгоритмике.
Яндекс например проводит (217) по результатам которого приглашает на работу. На собеседованиях у них я таких задач не видел, но попросить написать реализацию хеш-таблицы они на собеседовании вполне могут.
А что не так с задачей - я в упор не понимаю. Обычная задача на алгоритмику.

Соревнования по спортивному программированию для отбора программистов устраивают все крупные компании. Google Code Jam, Facebook Hacker Cup, Mail Code Cup (не путать с AI CUP), Яндекс Алгоритм, VK Cup  и т.д.
Им нужны специалисты с хорошей алгоритмикой. Ну и вузы по специальности "прикладная математика и информатика" готовят именно специалистов умеющих решать подобные задачи, потому что это востребовано рынком.  А в (0) несложная конечно, но хорошая алгоритмическая задача.

(219) Да-да-да. Целый вагон окружения в котором ты чо-то должен. Илита. Илита по лекалам.

И эти люди рассказывают про выпуск школы квадратноголовых.

Бля, задача в (0) это ссылка на конкретный курс и на конкретный его параграф. Она не оставляет пространства мысли. Тупой зубреж. Я наслушался таких в акамедии, хорош.

Лимит по памяти важен. Далеко не все интерпретируемые языки смогут запустить интерпретатор в этих ограничениях. Выбирайте инструмент в соответствии с задачей

Охеренное условие. А Билл говорил, что хватит 640мб. Или блин важнее решить на память а не на скорость. Чо за г-но?

(220, 223) Если я правильно понял, то такие задачи - типичные для вузовской подготовки. Ну, не дает мне покоя вопрос, а куда это тс поступает? Неужели в аспирантуру?

(224) там условие и по времени и по памяти. Как у любой подобной задачи.

(221) Да-да-да! Только 1Сники знают как правильно готовить программистов, и какие знания  навыки требуются гуглам-яндексам. Я бы на твоем месте предложил им свои услуги по правильному подбору персонала. Ведь тогда они и сами озолотятся, и тебя озолотят.
(223) Зубреж? Академии? Ничего что спортивные программисты выигрывают совревнования по промышленному программированию, на конкретных реальных задачах.
Ну и простой вопрос - ты на полном серьезе думаешь что олимпиадники это зубрежники? Второе название спортивного программирования - олимпиадное программирование. Олимпиады - школьные, студенческие - это соревнования именно по спортивному программированию.

(225) И для школьной.
Вот задачи всеросса ВОШ по информатике.
https://neerc.ifmo.ru/school/archive/2017-2018.html#roi
В самом низу
https://neerc.ifmo.ru/school/archive/2017-2018/ru-olymp-roi-2018-day1.pdf
https://neerc.ifmo.ru/school/archive/2017-2018/ru-olymp-roi-2018-day2.pdf

ну и спойлер, решения
https://neerc.ifmo.ru/school/archive/2017-2018/ru-olymp-roi-2018-analysis.pdf

Если кому интересно, прямо сейчас начинается финал VC Cup 2018 проводимого "вконтакте"
http://codeforces.com/blog/entry/61156
онлайн трансляция
http://codeforces.com/spectator/contest/951/standings
Важный день! Сегодня мы узнаем победителей VK Cup 2018. Призовой фонд чемпионата как и в прошлом году связаны с круглыми числами в двоичной системе счисления:
•1 место — 1048576 рублей
•2 местo — 524288 рублей
•3 местo — 262144 рубля
•4-8 места — 131072 рубля

Планируем начинать в 10:40.

(225) не я, дочка. см. личку. (в ней инфа нее менялась с момента создания).

Дочка уже поступила в МФТИ, без экзаменов.
И меня терзают смутные сомнения.
Правильно ли она сделала выбор.

(231) На прикладную математику и информатику?
А чего плохого в выборе?

Вот у меня сын отличный выбор сделал. БВИ, выбирал из ИТМО СПБГУ, СПбАУ. Выбрал третье, так как там состав студентов намного сильнее, они брали только победителей и призеров финала вош, с других олимпиад не брали.
Так в итоге факультет после этой сессии развалился!
Они полным составом, три курса бакалавриата, включая преподавателей и спонсоров (Яндекс) перешли в ВШЭ.
Утешает то, что не вуз делает студентов, а студенты, преподаватели и спонсоры делают вуз. Так что репутация ВШЭ в прикладной математике и информатики должна вырасти, и места на icpc acm улучшится.

я не представляю девчонку которая так парит мозги, ну или она очень слишком более лучше крутая.

(234) его год, прошлый год выпуска, одна из самых крутых в России - девушка.

Дроздова Алнксандра. Чемпион России (чистое первое место), серебрянный медалист чемпионата мира среди школьников.

Виноват, третье место в фиеале всеросса вош
http://roi2017.snarknews.info/index.cgi?data=roi/base/012487&head=index&menu=index&class=roi2017&year=2017&contest=roi

ВШЭ - высшая школа экономики?

(238) Да. ВШЭ далеко не на последнем месте по рейтингам по ПМиИТ, и нормально выступает на ACM ICPC, но чемпионом мира ни разу не была. Ну и такого факультета в Питере не было, они в этом году будут числиться в Москве, а учиться в Питере. И есть вероятность что из-за этого в этом году в чемпионате мира участвовать не удастся.
Но по большому счету главное все-таки программа обучения и преподаватели, а они остались прежними.
Ну и есть разница получить диплом ИТМО или СПбГУ,  которые многократные чемпионы мира по программированию, или ВШЭ.