Overview

We consider how much Takahashi has closed the gap with Aoki as “relative progress.”
Using the speed difference \(C_i = B_i - A_i\), we examine the increase/decrease per cycle.

Analysis

At time \(0\), Aoki is \(d\) ahead of Takahashi.

During a given 1-second interval:

• Aoki advances \(A_i\)
• Takahashi advances \(B_i\)

So the amount by which Takahashi closes the gap with Aoki is

\(C_i = B_i - A_i\)

Therefore, if the cumulative sum of \(C_i\) up to time \(t\) reaches \(d\) or more, Takahashi catches up with Aoki.

For example, if we let \(X\) be the accumulated relative progress:

• \(X < d\): has not caught up yet
• \(X \geq d\): has caught up

---

Here, the speed table has a period of \(N\) seconds.

Let \(C_i = B_i - A_i\), and define the total relative progress over one full cycle as

\(S = C_1 + C_2 + \cdots + C_N\)

Also, define the prefix sum from the beginning up to the \(r\)-th second within a cycle as

\(P_r = C_1 + C_2 + \cdots + C_r\)

The relative progress at time \(kN + r\) is

\(kS + P_r\)

Here, \(k\) represents how many full cycles have passed, and \(r\) represents which second within the cycle.

---

A naive second-by-second simulation won’t work in time because the answer can be extremely large.

On the other hand, since \(N \leq 3000\) and \(NQ \leq 10^7\), it is feasible to check all \(N\) positions within a cycle for each query.

---

We case-split as follows.

Case \(S \leq 0\)

Looking at one full cycle, Takahashi is not closing the gap with Aoki, or the gap is worsening.

In this case, for a position \(r\) within the cycle, the value in subsequent cycles is

\(kS + P_r\)

but since \(S \leq 0\), this does not increase as \(k\) grows.

In other words, if catching up is possible at all, it must happen within the first cycle.

Therefore, we search for the smallest \(r\) such that \(P_r \geq d\). If none exists, the answer is \(-1\).

Case \(S > 0\)

The relative progress increases by exactly \(S\) each cycle.

For each position \(r\) within the cycle, we find the minimum \(k\) such that

\(kS + P_r \geq d\)

which gives us the earliest time candidate for catching up at that position.

If \(P_r \geq d\), then \(k = 0\).

Otherwise,

\(k = \left\lceil \frac{d - P_r}{S} \right\rceil\)

The candidate time is

\(kN + r\)

so we check all \(r = 1, 2, \dots, N\) and output the minimum value as the answer.

Algorithm

First, for each \(i\), we store

\(C_i = B_i - A_i\)

Then we process each query in order.

Query 1 i a b

Since the \(i\)-th entry of the speed table is changed, we update

\(C_i = b - a\)

Query 2 d

For the current \(C\), we do the following:

1. Compute \(S = \sum C_i\)
2. If \(S \leq 0\):
   • Compute prefix sums \(P_r\) from the beginning
   • If there exists an \(r\) where \(P_r \geq d\) for the first time, that is the answer
   • Otherwise, \(-1\)
3. If \(S > 0\):
   • Compute \(P_r\) for each \(r = 1, 2, \dots, N\)
   • Determine the required number of cycles \(k\)
   • Use time \(kN + r\) as a candidate
   • Output the minimum value

Complexity

• Time complexity: \(O(NQ)\)
  • Update queries are \(O(1)\)
  • Answer queries are \(O(N)\)
  • Since the constraint guarantees \(NQ \leq 10^7\), this is fast enough
• Space complexity: \(O(N)\)

Implementation Notes

\(C_i = B_i - A_i\) can be negative.
Also, since the answer time can be very large, use long long.

The ceiling division for the case \(S > 0\) can be computed as:

(d - pref + S - 1) / S

However, this is only used when pref < d.
When pref >= d, the required number of cycles is \(0\).

Source Code

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;

    vector<ll> C(N);
    for (int i = 0; i < N; i++) {
        ll A, B;
        cin >> A >> B;
        C[i] = B - A;
    }

    while (Q--) {
        int type;
        cin >> type;

        if (type == 1) {
            int i;
            ll a, b;
            cin >> i >> a >> b;
            --i;
            C[i] = b - a;
        } else {
            ll d;
            cin >> d;

            ll S = 0;
            for (ll x : C) S += x;

            if (S <= 0) {
                ll pref = 0;
                ll ans = -1;
                for (int i = 0; i < N; i++) {
                    pref += C[i];
                    if (pref >= d) {
                        ans = i + 1;
                        break;
                    }
                }
                cout << ans << '\n';
            } else {
                const ll INF = 4'000'000'000'000'000'000LL;
                ll pref = 0;
                ll ans = INF;

                for (int i = 0; i < N; i++) {
                    pref += C[i];

                    ll k = 0;
                    if (pref < d) {
                        k = (d - pref + S - 1) / S;
                    }

                    ll t = k * (ll)N + (i + 1);
                    ans = min(ans, t);
                }

                cout << ans << '\n';
            }
        }
    }

    return 0;
}

---

This editorial was generated by gpt-5.5-xhigh.