Задача №114113. Просмотр сериалов
Сегодня у Алёны выходной, а значит ничто не помешает ей заниматься любимым делом — смотреть сериалы по телевизору. В течение всего дня на канале А будут показывать новый сезон сериала «Борьба табуреток», а на канале Б новый сезон сериала «Дворец из домино». Поскольку Алёна не может выбрать, какой из этих двух сериалов ей нравится больше, то она решила попробовать смотреть оба, переключаясь на другой канал каждый раз, когда начинается реклама.
В момент времени 0 Алёна включит телевизор и начнёт смотреть сериал «Борьба табуреток» по каналу А. Если в какой-либо момент времени на телеканале, который Алёна сейчас смотрит, начнётся реклама, то Алёна переключит телевизор на другой телеканал и будет смотреть его. Если Алёна переключает телеканал, а там тоже в данный момент идёт реклама, то она не станет переключаться обратно в надежде, что на этом канале реклама закончится раньше. В момент времени t Алёна выключит телевизор и пойдёт спать.
По заданному расписанию показа рекламы и продолжительности одного рекламного ролика определите, какое количество единиц времени Алёна будет смотреть каждый из сериалов.
В первой строке входных данных записаны четыре целых числа n , m , t и k ( 1 ≤ n , m ≤ 100 000 , 1 ≤ t ≤ 10 18 , 1 ≤ k ≤ 10 9 ) — количество показов рекламы на канале А, количество показов рекламы на канале Б, момент времени, когда Алёна пойдёт спать и продолжительность одного рекламного ролика на любом из каналов соответственно.
Во второй строке записаны n целых чисел a 1 , a 2 , ..., a n ( 1 ≤ a i ≤ 10 18 ), определяющих моменты времени, когда на канале А начнётся показ рекламы. Гарантируется, что моменты времени следуют в порядке возрастания, и что между любыми двумя рекламными роликами ненулевое количество времени показывается сериал, то есть a i + k < a i + 1 для любого i от 1 до n - 1 .
В третьей строке записаны m целых чисел b 1 , b 2 , ..., b m ( 1 ≤ b i ≤ 10 18 ), определяющих моменты времени, когда на канале Б начнётся показ рекламы. Как и для канала А, для канала Б гарантируется, что моменты времени следуют в порядке возрастания, и что между любыми двумя рекламными роликами идёт сериал в течение ненулевого отрезка времени.
Выведите два целых числа, равных суммарному количеству времени, которое Алёна будет смотреть сериал «Борьба табуреток» и сериал «Дворец из домино» соответственно.
Тесты к этой задаче состоят из трёх групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп.
В первом примере реклама на обоих каналах всегда начинается одновременно, поэтому, хотя Алёна и переключит канал в момент времени 4 , она будет смотреть рекламу в течение трёх моментов времени. Затем она снова переключит канал в момент времени 8 , но уже не дождётся конца рекламы и уйдёт спать.
Во втором примере Алёна будет переключать каналы таким образом, что ей никогда не придётся смотреть рекламу.
2 2 10 3 4 8 4 8
4 1
6 5 10 1 1 3 5 7 9 11 2 4 6 8 10
5 5