First, one can find the set of intervals \(S _ i\) in which each person was in the office.

We set a threshold \(C\) to choose one of the following two algorithms depending on whether the size of \(S _ i\) is greater than \(C\):

• if \(S _ A\) and \(S _ B\) both have sizes less than \(C\)
• if at least one of \(S _ A\) or \(S _ B\) has a size at least \(C\)

if \(S _ A\) and \(S _ B\) both have sizes less than \(C\)

By scanning the intervals in ascending order of their left ends, one can find the answers in \(O( C)\) time.

if at least one of \(S _ A\) or \(S _ B\) has a size at least \(C\)

There are at most \(\dfrac{N^2}C\) such pairs \((A,B)\). By precalculating the answer for all of them, one can respond the query in \(O(1)\) time.

There are at most \(\dfrac NC\) indices \(i\) such that the size of \(S _ i\) is greater than or equal to \(C\). For each of these \(i\), one can scan all the records to find the answers for all people. This precomputation can be done in \(O\left(\dfrac{MN}C\right)\) time with \(O\left(\dfrac{N^2}C\right)\) memory.

Since the overall time complexity is \(O\left(QC+\dfrac{MN}C\right)\), picking \(C=O\left(\sqrt{\dfrac{MN}Q}\right)\) makes the time complexity \(O(\sqrt{QMN})\), which is fast enough.

The sample code is as follows.

#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>

int main() {
    using namespace std;
    unsigned N, M;
    cin >> N >> M;
    vector<pair<unsigned, unsigned>> records(M);
    for (auto &&[T, P]: records) {
        cin >> T >> P;
        --P;
    }
    vector<vector<pair<unsigned, unsigned>>> inside_office(N);
    {
        vector<unsigned> in(N);
        for (const auto &[T, P]: records) {
            if (in[P]) {
                inside_office[P].emplace_back(in[P], T);
                in[P] = 0;
            } else
                in[P] = T;
        }
    }
    constexpr unsigned large_limit{1000};
    map<pair<unsigned, unsigned>, unsigned> memo;

    // Find the answer for the larger set
    for (unsigned i{}; const auto &Si : inside_office) {
        if (size(Si) > large_limit) {
            vector<unsigned> sum(N);
            // Records how many minute person i stayed in the office so far
            unsigned prev_i{}, i_sum{};
            bool i_inside{false};
            // Use cumulative sums to find the time when person P and person i stayed in the office together
            for (const auto &[T, P]: records) {
                if (P == i) {
                    i_sum += i_inside * (T - prev_i);
                    prev_i = T;
                    i_inside ^= true;
                }
                sum[P] = i_sum + i_inside * (T - prev_i) - sum[P];
            }
            for (unsigned j{}; j < N; ++j)
                memo[minmax(i, j)] = sum[j];
        }
        ++i;
    }

    // Find the answer for small set sizes
    const auto query{[&inside_office, &memo](unsigned a, unsigned b) {
        if (memo.contains({a, b}))
            return memo[{a, b}];
        const auto &Sa{inside_office[a]};
        const auto &Sb{inside_office[b]};
        // If either is empty, then the answer is no
        if (empty(Sa) || empty(Sb))
            return memo[{a, b}] = 0;
        unsigned ans{};
        // Inspect the segments for a and b in ascending order, and find the sum of the lengths of union.
        for (unsigned i{}; const auto &[l, r] : Sa){
        ans += clamp(Sb[i].second, l, r) - clamp(Sb[i].first, l, r);
        while (i + 1 < size(Sb) && Sb[i + 1].first <= r) {
            ++i;
            ans += clamp(Sb[i].second, l, r) - clamp(Sb[i].first, l, r);
        }
    }
        return memo[{a, b}] = ans;
    }};

    unsigned Q;
    cin >> Q;

    for (unsigned i{}, a, b; i < Q; ++i) {
        cin >> a >> b;
        --a;
        --b;
        cout << query(a, b) << endl;
    }
    return 0;
}