1. Идея

Нужно для каждой пары дат найти разность d2 - d1 в днях.

Самый удобный способ — не считать дни "между датами" напрямую, а для каждой даты отдельно вычислить её порядковый номер: сколько дней прошло от некоторого очень раннего начала отсчёта до этой даты. Тогда ответ для запроса будет просто:

serial(d2) - serial(d1)

Это автоматически даёт:

• 0, если даты равны;
• положительное число, если d2 позже;
• отрицательное число, если d2 раньше.

2. Наблюдения

1. Високосный год определяется по стандартному правилу

Год високосный, если:

• делится на 4 и не делится на 100,
• или делится на 400.

Например:

• 2000 — високосный;
• 1900 — не високосный;
• 2004 — високосный.

2. Количество дней до начала года можно посчитать формулой

Пусть нужно узнать, сколько дней прошло до 1 января года y.

До этого момента полностью прошли годы 1, 2, ..., y - 1, то есть n = y - 1 лет.

Если бы все годы были обычными, было бы 365 * n дней.

Но нужно добавить количество високосных лет среди этих n лет:

• лет, кратных 4: n // 4
• но годы, кратные 100, не високосные: вычитаем n // 100
• годы, кратные 400, всё-таки високосные: добавляем n // 400

Получаем:

days_before_year(y) = 365 * (y - 1) + (y - 1) // 4 - (y - 1) // 100 + (y - 1) // 400

3. Дни до начала месяца тоже можно хранить заранее

Если год невисокосный, то количество дней до начала каждого месяца фиксировано:

• до января: 0
• до февраля: 31
• до марта: 59
• до апреля: 90
• ...
• до декабря: 334

Это удобно записать в массив pref, где pref[m] — сколько дней прошло до начала месяца m в обычном году.

4. Для дат после февраля в високосном году нужно добавить ещё один день

Если дата находится в марте или позже, а год високосный, то 29 февраля уже прошёл, значит нужно прибавить 1.

5. День месяца добавляется как d - 1

Например:

• 1 января должно иметь сдвиг 0 внутри своего месяца;
• 2 января — 1;
• 31 января — 30.

Поэтому к сумме прибавляется d - 1.

3. Алгоритм

Для каждой даты YYYY-MM-DD:

1. Разбираем строку:

   • year = s[0:4]
   • month = s[5:7]
   • day = s[8:10]

2. Считаем её серийный номер:

   • берём число дней до начала года;
   • прибавляем число дней до начала месяца;
   • если month >= 3 и год високосный, прибавляем 1;
   • прибавляем day - 1.

3. Для запроса выводим:

   • serial(d2) - serial(d1)

4. Почему это работает

Докажем корректность.

Рассмотрим функцию serial(y, m, d). Она считает количество дней, прошедших до даты y-m-d, не включая сам текущий день.

Эта величина состоит из трёх частей:

1. days_before_year(y) — все дни в годах до y.
2. pref[m] — все дни в месяцах до m внутри года y, если считать год обычным.
3. Поправка на високосный год:
   • если дата в марте или позже и год високосный, то внутри этого года уже был дополнительный день 29 февраля, значит добавляем 1.
4. d - 1 — сколько дней прошло внутри текущего месяца до даты d.

Таким образом, serial(y, m, d) действительно равен количеству дней от начала выбранной шкалы до данной даты.

Тогда разность

serial(d2) - serial(d1)

равна числу дней, которое нужно пройти от d1 до d2.

Если даты одинаковые, разность равна 0. Если d2 позже, разность положительна. Если d2 раньше, разность отрицательна.

Значит, алгоритм решает задачу правильно.

5. Сложность

Пусть запросов q.

Для каждого запроса:

• разбор двух строк даты занимает O(1);
• вычисление двух серийных номеров занимает O(1).

Итоговая сложность:

• по времени: O(q)
• по памяти: O(1), не считая хранения входных строк

Это легко укладывается в ограничения до 10^5 запросов.

6. Код на C++17

#include <iostream>
#include <string>
#include <vector>

using namespace std;

bool isLeap(long long y) {
    return (y % 4 == 0 && y % 100 != 0) || (y % 400 == 0);
}

long long daysBeforeYear(long long y) {
    long long n = y - 1;
    return 365LL * n + n / 4 - n / 100 + n / 400;
}

long long serialDate(long long y, int m, int d) {
    static int pref[13] = {
        0,
        0,
        31,
        59,
        90,
        120,
        151,
        181,
        212,
        243,
        273,
        304,
        334
    };

    long long res = daysBeforeYear(y);
    res += pref[m];
    if (m >= 3 && isLeap(y)) {
        res += 1;
    }
    res += d - 1;
    return res;
}

void parseDate(const string& s, long long& y, int& m, int& d) {
    y = stoll(s.substr(0, 4));
    m = stoi(s.substr(5, 2));
    d = stoi(s.substr(8, 2));
}

int main() {
    int q;
    cin >> q;

    for (int i = 0; i < q; i++) {
        string a, b;
        cin >> a >> b;

        long long y1, y2;
        int m1, d1, m2, d2;

        parseDate(a, y1, m1, d1);
        parseDate(b, y2, m2, d2);

        long long s1 = serialDate(y1, m1, d1);
        long long s2 = serialDate(y2, m2, d2);

        cout << (s2 - s1) << "\n";
    }

    return 0;
}

7. Код на Python 3

def is_leap(y):
    return (y % 4 == 0 and y % 100 != 0) or (y % 400 == 0)

def days_before_year(y):
    n = y - 1
    return 365 * n + n // 4 - n // 100 + n // 400

pref = [0, 0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334]

def serial_date(y, m, d):
    res = days_before_year(y)
    res += pref[m]
    if m >= 3 and is_leap(y):
        res += 1
    res += d - 1
    return res

def parse_date(s):
    y = int(s[0:4])
    m = int(s[5:7])
    d = int(s[8:10])
    return y, m, d

q = int(input())
for _ in range(q):
    a, b = input().split()
    y1, m1, d1 = parse_date(a)
    y2, m2, d2 = parse_date(b)
    s1 = serial_date(y1, m1, d1)
    s2 = serial_date(y2, m2, d2)
    print(s2 - s1)