Задача №115379. Крайний Банк
Крайний банк занимается важной деятельностью — контролем биржей бипок и обнаружением потенциального мошенничества. Вам, как стажеру Крайнего Банка, поручили разработать систему, которая позволяла бы определять, является ли данный трейдер потенциальным мошенником или нет. Вы знаете, что биржа бипок работала \(n\) моментов времени, в течение которых трейдер торговал на бирже.
Вам известно, что в \(i\)-й момент времени цена одной бипки составляла \(a_i\) и трейдер продал или купил \(|b_i|\) бипок по данной цене. Если \(b_i < 0\), то он продал \(-b_i\) бипок, а если \(b_i > 0\), то купил \(b_i\) бипок. На момент начала торгов у трейдера было \(0\) бипок, а также известно, что к концу торгов он распродал все бипки (другими словами, сумма \(b_i\) равна \(0\)). Также трейдер не мог уходить в минус, то есть в любой момент времени у него было неотрицательное количество бипок. Если \(b_i = 0\), то в \(i\)-й день трейдер не продавал и не покупал бипки.
Крайний банк считает трейдера потенциальным мошенником, если каждой операции покупки одной конкретной бипки можно сопоставить в пару операцию продажи одной бипки так, что покупка произошла раньше продажи и стоимость покупки строго меньше стоимости продажи. Обратите внимание, что разным операциям покупки одной бипки должны соответствовать разные операции продажи. При этом, если две бипки были куплены в один и тот же момент времени, операции продажи для них могли произойти в разное время.
Определите, является ли данный трейдер потенциальным мошенником.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число \(t\) (\(1 \le t \le 10\,000\)) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число \(n\) (\(2 \leq n \leq 200\,000\)) — количество моментов времени, в течение которых трейдер торговал на бирже.
Вторая строка каждого набора входных данных содержит \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) (\(1 \leq a_i \leq 10^9\)) — стоимость одной бипки в \(i\)-й момент времени.
Третья строка каждого набора входных данных содержит \(n\) целых чисел \(b_1, b_2, \ldots, b_n\) (\(-10^9 \leq b_i \leq 10^9\)) — числа, характеризующие операции покупки/продажи, совершенные трейдером, в соответствии с форматом, описанным в условии.
Гарантируется, что в любой момент времени у трейдера было неотрицательное количество бипок, а также \(b_1 + b_2 + \ldots + b_n = 0\).
Гарантируется, что сумма \(n\) по всем наборам входных данных не превосходит \(200\,000\).
Для каждого набора входных данных выведите « Yes » (без кавычек), если трейдер является потенциальным мошенником, иначе выведите « No » (без кавычек).
Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки « yEs », « yes », « Yes » и « YES » будут приняты как положительный ответ.
В данной задаче \(25\) тестов, помимо тестов из условия, каждый из них оценивается в \(4\) балла. Результаты работы ваших решений на всех тестах будут доступны сразу во время соревнования.
Обозначим за \(N\) сумму \(n\) по всем наборам входных данных в данном тесте.
Решения, корректно работающие при \(n \leq 7\), \(t \leq 10\), наберут не менее \(24\) баллов.
Решения, корректно работающие при \(N \leq 3000\), наберут не менее \(60\) баллов.
Решения, корректно работающие при \(a_i \leq 3\), наберут не менее \(28\) баллов.
В первом наборе входных данных трейдер продает бипки, купленные по цене \(2\) и \(3\) по цене \(2\). Тем самым он не выходит в плюс по каждой бипке и не является потенциальным мошенником.
Во втором наборе входных данных трейдер продает бипки, купленные по цене \(2\) и \(3\) по цене \(4\). Тем самым он выходит в плюс по каждой бипке и является потенциальным мошенником.
В третьем наборе входных данных трейдер может продать в третий момент времени бипку, купленную по цене \(2\) за \(3\) и выйти по ней в плюс. После чего в пятый момент времени продать все остальные бипки и выйти по ним в плюс. Таким образом, он является потенциальным мошенником.
4 3 2 3 2 1 1 -2 3 2 3 4 1 1 -2 5 2 3 3 3 4 1 1 -1 1 -2 2 1000000000 1000000000 1000000000 -1000000000
No Yes Yes No