To Play or not to Play
Contest: Russian Code Cup 2017 - Finals [Unofficial Mirror, Div. 1 Only Recommended, Teams Allowed]
Difficulty rating: 3000
Tags: greedy

Vasya and Petya are playing an online game. As most online games, it has hero progress system that allows players to gain experience that make their heroes stronger. Of course, Vasya would like to get as many experience points as possible. After careful study of experience points allocation, he found out that if he plays the game alone, he gets one experience point each second. However, if two players are playing together, and their current experience values differ by at most C points, they can boost their progress, and each of them gets 2 experience points each second.

Since Vasya and Petya are middle school students, their parents don't allow them to play all the day around. Each of the friends has his own schedule: Vasya can only play during intervals [a1;b1], [a2;b2], ..., [an;bn], and Petya can only play during intervals [c1;d1], [c2;d2], ..., [cm;dm]. All time periods are given in seconds from the current moment. Vasya is good in math, so he has noticed that sometimes it can be profitable not to play alone, because experience difference could become too big, and progress would not be boosted even when played together.

Now they would like to create such schedule of playing that Vasya's final experience was greatest possible. The current players experience is the same. Petya is not so concerned about his experience, so he is ready to cooperate and play when needed to maximize Vasya's experience.

Input format:
The first line of input data contains integers n, m and C — the number of intervals when Vasya can play, the number of intervals when Petya can play, and the maximal difference in experience level when playing together still gives a progress boost (1 ≤ n, m ≤ 2·105, 0 ≤ C ≤ 1018).

The following n lines contain two integers each: ai, bi — intervals when Vasya can play (0 ≤ ai < bi ≤ 1018, bi < ai + 1).

The following m lines contain two integers each: ci, di — intervals when Petya can play (0 ≤ ci < di ≤ 1018, di < ci + 1).

Output format:
Output one integer — the maximal experience that Vasya can have in the end, if both players try to maximize this value.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
2 1 5
1 7
10 20
10 20

Example output:
25

Example input:
1 2 5
0 100
20 60
85 90

Example output:
125

Editorial:
Перейдем в координаты y(x), где x — exp1 - exp2, а y — exp1 (exp1, exp2 — опыт первого и второго игроков в некоторый момент времени соответственно). Будем идти по отрезкам времени и поддерживать множество достижимых состояний на этой плоскости.
Лемма 1: есть оптимальное решение, в котором на всех отрезках, где могут играть оба, оба играют (доказательство в конце).
Есть три перехода:
• Может играть лишь первый игрок t времени. Это значит, что новый многоугольник — сумма Минковского старого многоугольника и вырожденного многоугольника на двух вершинах (0, 0) и (t, t).
• Может играть лишь второй игрок t времени. Это значит, что новый многоугольник — сумма Минковского старого многоугольника и вырожденного многоугольника на двух вершинах (0, 0) и ( - t, 0).
• Могут играть оба игрока t времени. Поскольку не выгодно, чтобы играл лишь один из них (лемма 1), нужно всем точкам с координатами в [ - C;C] прибавить 2t в y-координату, а остальным точкам прибавить t в y-координату.
Посмотрим на структуру множества достижимых точек. Это многоугольник, монотонный относительно оси OX (любая прямая параллельная OY пересекает его в  ≤ 2 точках), при чем нижняя ломаная этого многоугольника — y = 0 при x ≤ 0 и y = x при x > 0. Эти два факта непосредственно следуют из того, что все три операции сохраняют эти инварианты. Таким образом, нам интересно следить лишь за верхней огибающей многоугольника.
Покажем, что y-координата верхней части многоугольника у нас будет не убывать с ростом x-координаты, и состоит верхняя часть ломаной из векторов (+1,0) и (+1,+1). Пусть по индукции это верно.
После переходов первых двух типов монотонность сохраняется на всей ломаной: первый переход лишь сдвигает старую верхнюю часть ломаной на (+1, +1), а второй переход сдвигает верхнюю часть ломаной на (-1,0). Но вот операция третьего типа может нарушить монотонность в точке x = C, так там происходит сдвиг по OY на разные величины. Исправим это, несколько изменив смысл многоугольника, который мы поддерживаем: если раньше это было множество всех достижимых состояний, то теперь будем поддерживать монотонное множество точек, возможно не все из которых можно получить, но имеющее такой же максимальный достижимый опыт из любой точки множества.
Для этого докажем лемму: если в момент времени t взять две точки (не важно, достижимы ли они к моменту времени t) P1 = (x1, y1) и P2 = (x2, y2) такие, что C ≤ x1 ≤ x2, и y1 ≥ y2, то ответ для точки P2 не больше, чем ответ для точки P1. Для этого возьмем сертификат, ведущий к оптимальному ответу из точки P2 — это некоторая последовательность переходов первого, второго и третьего типа, и выкинем из нее первых переходов второго типа ровно на x2 - x1 (единственных, уменьшающих x). Можно заметить, что полученный сертификат — корректный набор действий из точки P1, и имеет такой же сдвиг по y, так как области двойного опыта будут ровно такими же (до момента совпадения x-координат его быть не может, т.к. x2 - C ≥ x2 - x1, а с этого момента времени графики движения будут совпадать).
Таким образом, после операции третьего типа можно взять на суффиксе x для [C; + inf) максимум между сдвинутой ломаной и прямой y = y(C). Абсолютно аналогично доказывается, что ломаную можно промажорировать прямой y = y(C) - (C - x) на отрезке ( - inf;C].
Таким образом, после перехода ломаная все еще осталась монотонно неубывающей, состоящей из ребер (+1,0) и (+1,+1).
Для решения задачи нужно научиться быстро совершать необходимые переходы с этой ломаной.
Легко заметить, что в ней линейное число вершин, так как все операции добавляют константное число новых ребер: первые две не изменяют количество вершин ломаной, а третья создает два новых ребра и, возможно, выкидывает несколько старых.
Можно хранить ломаную в декартовом дереве — тогда легко разрезать ломаную в точках  - C и  + C, вставить в нужное место новые ребра и удалить несколько старых. Таким образом, получили решение, работающее за O(nlogn).
Лемма 1, доказательство: рассмотрим оптимальное решение, и посмотрим на первый отрезок, где могли играть оба, но играет лишь один. Если |x| = |exp1 - exp2| ≤ C, это делать точно не выгодно. Иначе, для определенности, x <  - C. Понятно, что в оптимальном решении точка еще вернется в полосу |x| ≤ C (иначе оба могут спокойно играть). Если сейчас играет лишь первый игрок (прибавляется вектор (+1, +1)), то раньше, естественно, был момент после последнего посещения полосы двойного опыта, когда играл лишь второй игрок (вектор (-1, 0)). Пусть в тот момент второй игрок не играл, а сейчас играют оба, итоговая позиция сохраняется, а первый момент, когда играет один, но не оба, отдалился. Случаи, когда играет лишь первый игрок, и x > C, разбираются абсолютно аналогично, убирая момент времени, когда играет лишь один из игроков, но добавляя момент, когда играют оба.