Subtask 1 : ~1 \leq T \leq 10^6~.

Ta duyệt từng thời điểm ~i \in [0, T)~. Gọi ~x~, ~y~ là hai vị trí lớn nhất mà ~a_x, b_y \leq i~, và ~s = 0/1~ là trạng thái đang xem TV ở A/B.

Ta sẽ có các trường hợp sau:

• Nếu ~s = 0, a_x = i~ hoặc ~s = 1, b_y = i~ thì đang có quảng cáo tại thời điểm ~i~. Lúc này, ta sẽ chuyển sang xem TV ở chương trình còn lại ~(s = 1 - s)~, nếu tại thời điểm đó chương trình còn lại cũng có quảng cáo thì ta nhảy ~i~ đến thời điểm kết thúc quảng cáo.
• Ngược lại, ta sẽ tăng đáp án cho thời gian xem TV ở A/B ứng với ~s = 0/1~.

Ta có thể duy trì hai biến ~x, y~ bằng kỹ thuật hai con trỏ do mảng ~a, b~ đã được sắp xếp. Độ phức tạp: ~O(n + m + T)~.

Subtask 2: ~1 \leq n, m \leq 2*10^5, 1 \leq T \leq 10^{18}~.

Ta vẫn duyệt các quãng thời gian như thế, tuy nhiên ta không "chờ" để đến thời gian xem quảng cáo, mà ta sẽ nhảy thẳng đến thời điểm đó. Độ phức tạp: ~O(n + m)~.

Code tham khảo:

int x = 1, y = 1, cur = 0;
ll ansA = 0, ansB = 0;
a[n + 1] = b[m + 1] = t;
ll i = 0;
while(i < t) {
    while(x <= n && a[x + 1] <= i) x++;
    while(y <= m && b[y + 1] <= i) y++;
    if ((cur == 0 && a[x] == i) || (cur == 1 && b[y] == i)) {
        cur = cur ^ 1;
        bool ok = false;
        if (cur == 0 && a[x] <= i && a[x] + k >= i) i = a[x] + k, ok = true;
        if (cur == 1 && b[y] <= i && b[y] + k >= i) i = b[y] + k, ok = true;
        if (ok) continue;
    }
    if (cur == 0) {
        if (a[x] > i) ansA += a[x] - i, i = a[x];
        else ansA += a[x + 1] - i, i = a[x + 1];
    }
    else {
        if (b[y] > i) ansB += b[y] - i, i = b[y];
        else ansB += b[y + 1] - i, i = b[y + 1];
    }
}