Страница: 1 Отображать по:
#3204
Отрезки на прямой возвращаются
  

На прямой задано \(N\) попарно различных отрезков \([a_i, b_i]\) (\(i = 1, 2, \dots, N\), \(a_i < b_i\)). Будем говорить, что отрезок номер \(i\) непосредственно содержится в отрезке номер \(j\) (\(i \ne j\)), если:

  • он полностью принадлежит \(j\)-му (то есть \(a_j \le a_i\) и \(b_i \le b_j\)),
  • среди заданных \(N\) отрезков не найдётся такого отрезка (с номером \(k\)), что \(i\)-й отрезок принадлежит \(k\)-му и \(k\)-й принадлежит \(j\)-му (здесь \(i\), \(j\) и \(k\) - различные числа).

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

Входные данные

Сначала вводится целое число \(N\) (\(1 \le N \le 100\,000\)). Далее идут \(N\) пар целых чисел \(a_i\), \(b_i\) (\(-10^9 \le a_i < b_i \le 10^9\)).

Выходные данные

Выведите \(N\) чисел. Число номер \(i\) должно быть равно номеру отрезка, в котором непосредственно содержится отрезок номер \(i\), либо 0 - если такого не существует.

Если существует несколько решений, выведите любое.

Примечания

Тесты состоят из четырёх групп.

  1. Тест 1, из условия, оценивается в 0 баллов.
  2. Тесты 2--11. В них \(N \le 100\). Группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
  3. Тесты 12--27. В них \(N \le 10\,000\). Группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
  4. Тесты 28--35. Off-line группа, полные ограничения. Каждый тест оценивается в 5 баллов (тесты оцениваются независимо друг от друга). При этом баллы за тесты этой группы ставятся только тогда, когда программа проходит все тесты групп 1 и 2. Если программа не проходит хотя бы один из тестов групп 1 и 2, то баллы за тесты группы 3 не ставятся.
Примеры
Входные данные
4
2 3
0 4
1 6
0 5
Выходные данные
3 4 0 0
#3205
Отрезки на прямой возвращаются--2
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

При написании программы, проверяющей ответ участника для задачи 3204 "Отрезки на прямой возвращаются" (ссылка на задачу) (прочитайте её условие!), жюри столкнулось с трудностями, превосходящими сложность самой задачи. С мыслью "почему бы и нет" написание такой программы было решено также включить в комплект задач.

Проверяющей программе доступно три блока информации:

  • входные данные в формате, описанном в условии предыдущей задачи,
  • ответ некоторого абстрактного участника в формате, также описанном в предыдущем условии,
  • ответ жюри.

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

Входные данные

Вход состоит из трёх частей. Первая часть - число \(N\) (\(1 \le N \le 100\,000\)) и следом \(N\) пар \(a_i\), \(b_i\) (\(-10^9 \le a_i \lt b_i \le 10^9\)). Далее идут \(N\) чисел, каждое из которых от 0 до \(N\), \(i\)-е равно номеру отрезка, являющегося одним из непосредственно содержащих \(i\)-й, либо нулю - по мнению абстрактного участника. Далее идут ещё \(N\) чисел в том же формате - ответ жюри на эту задачу.

Входные данные всегда корректны. Это означает, например, что ответ участника не нужно проверять на соответствие формату и что ответ жюри точно правильный.

Выходные данные

Выведите \(N\) строк. В \(i\)-й строке должен быть вердикт для \(i\)-го отрезка. Выведите OK, если ответ абстрактного участника правильный, и WA - иначе.

Примечания

Тесты состоят из четырёх групп.

  1. Тест 1, из условия, оценивается в 0 баллов.
  2. Тесты 2--11. В них \(N \le 100\). Группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
  3. Тесты 12--27. В них \(N \le 10\,000\). Группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
  4. Тесты 28--35. Полные ограничения. Каждый тест оценивается в 5 баллов (тесты оцениваются независимо друг от друга). При этом баллы за тесты этой группы ставятся только тогда, когда программа проходит все тесты групп 1 и 2. Если программа не проходит хотя бы один из тестов групп 1 и 2, то баллы за тесты группы 3 не ставятся.
Примеры
Входные данные
4
2 3
0 4
1 6
0 5
2 2 1 0
3 4 0 0
Выходные данные
OK
WA
WA
OK
#3334
Проходной балл
  

Одна Очень Престижная Олимпиада, как и все престижные олимпиады в последнее время, состоит из двух туров - регионального и заключительного. Правила отбора во второй тур (заключительный этап) просты:

  1. Призеры олимпиады прошлого года приглашаются на заключительный этап вне зависимости от набранных ими в первом туре баллов.
  2. Все участники, набравшие не меньше баллов, чем установленный жюри проходной балл, проходят во второй тур.
  3. Если в каком-либо из регионов ни один участник по первым двум правилам во второй тур не прошел, то на заключительный этап приглашается участник из этого региона, набравший в нем максимальное количество баллов (это не касается регионов, от которых участников не было).
  4. На второй тур можно пригласить не более \(M\) участников.

Известно, что никакие два участника не набрали одинаковое количество баллов. По информации о результатах первого тура помогите жюри установить минимально возможный проходной балл, при котором все правила отбора будут выполнены.

Входные данные

В первой строке входного файла содержатся три целых числа \(N\), \(M\) и \(R\) - число участников первого тура, максимально возможное число участников второго тура и число регионов, из которых могли быть участники (\(1 \le M < N\)). Далее в \(N\) строках содержатся результаты каждого из участников. Каждая строка состоит из четырех целых чисел. Сначала идет \(id\) - уникальный идентификатор участника (\(1 \le id \le N\)), далее номер региона \(region\), в котором данный участник учится (\(1 \le region \le R\)), затем \(score\) - число баллов, набранных участником, четвертое число равно 1, если участник является призером олимпиады прошлого года, и 0 - в противном случае.

Гарантируется, что все идентификаторы участников различны, никакие два участника не набрали одинаковое число баллов, и выполнить все правила отбора возможно.

Выходные данные

Выведите одно число - минимальный проходной балл, который можно установить.

Примечания

Тесты состоят из четырёх групп. Во всех тестах \(0 \le score \le 10^9\).

  1. Тест 1 из условия, оценивается в 0 баллов.
  2. В тестах этой группы все числа на входе не превосходят 1000. Эта группа оценивается в 30 баллов, при этом баллы начисляются только при прохождении всех тестов группы.
  3. В тестах этой группы \(1 \le R \le M \le 10\,000\), \(M < N \le 100\,000\). Эта группа также оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
  4. В тестах этой группы, \(1 \le R \le M < N \le 100\,000\). Баллы за тесты этой группы начисляются только при прохождении всех тестов 1-й и 2-й групп. Каждый из тестов оценивается независимо от других.
Примеры
Входные данные
9 6 5
6 1 799 0
2 4 995 0
1 4 989 1
7 2 538 0
5 4 984 0
8 2 1000 0
3 2 998 0
4 2 823 1
9 1 543 0
Выходные данные
985
#3335
Лыжные гонки
  

Во время лыжных соревнований \(N\) спортсменов стартуют с интервалом в 1 минуту. Скорость каждого лыжника на дистанции постоянна: \(i\)-й лыжник преодолевает 1 км за \(w_i\) минут. Длина трассы равна \(L\) км. Считается, что \(i\)-й лыжник обогнал \(j\)-го (совершил обгон), если он стартовал позже \(j\)-го, а пришёл к финишу раньше него. Подсчитайте суммарное число совершённых во время гонки обгонов.

Входные данные

Первая строка входного файла содержит два целых числа \(N\) и \(L\). Во второй строке через пробел расположены \(N\) целых чисел \(w_i\).

Выходные данные

Выведите единственное число - суммарное количество обгонов.

Примечания

Во всех тестах \(1 \le L \le 10^9\), \(1 \le w_i \le 10^9\) при \(i = 1, 2, \dots, N\). Тесты состоят из трёх групп.

  1. Тесты 1 и 2 из условия, оцениваются в 0 баллов.
  2. В тестах этой группы \(1 \le N \le 10\,000\), эти тесты оцениваются в 50 баллов, при этом баллы начисляются только при прохождении всех тестов группы.
  3. Off-line группа, \(1 \le N \le 500\,000\). При этом баллы за тесты этой группы ставятся только тогда, когда программа проходит все тесты предыдущей группы. Если программа не проходит хотя бы один из тестов группы 1, то баллы за тесты группы 2 не ставятся. Тесты этой группы оцениваются независимо друг от друга.
Примеры
Входные данные
2 1
20 19
Выходные данные
0
Входные данные
5 3
3 6 2 4 1
Выходные данные
7
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест