概要

高橋君が青木君にどれだけ近づいたかを「相対的な進み」として考えます。
速さの差 \(C_i = B_i - A_i\) を使って、周期ごとの増減を調べます。

考察

時刻 \(0\) で青木君は高橋君より \(d\) だけ前にいます。

ある \(1\) 秒間で、

• 青木君は \(A_i\) 進む
• 高橋君は \(B_i\) 進む

ので、高橋君が青木君との差を縮める量は

\(C_i = B_i - A_i\)

です。

したがって、時刻 \(t\) までの \(C_i\) の累積和が \(d\) 以上になれば、高橋君は青木君に追い付きます。

例えば、累積した相対的な進みを \(X\) とすると、

• \(X < d\)：まだ追い付いていない
• \(X \geq d\)：追い付いた

となります。

---

ここで、速さの表は \(N\) 秒周期です。

\(C_i = B_i - A_i\) として、1周期全体での相対的な進みを

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

とします。

また、周期内の先頭から \(r\) 秒目までの累積和を

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

とします。

時刻 \(kN + r\) における相対的な進みは

\(kS + P_r\)

です。

ここで \(k\) は何周期終えたか、\(r\) は周期内の何秒目かを表します。

---

素朴に1秒ずつシミュレーションすると、答えが非常に大きくなる可能性があるため間に合いません。

一方で、\(N \leq 3000\) かつ \(NQ \leq 10^7\) なので、各クエリごとに周期内の \(N\) 個を全て調べることは可能です。

---

場合分けをします。

\(S \leq 0\) の場合

1周期全体で見ると、高橋君は青木君との差を縮められていない、または悪化しています。

このとき、同じ周期内の位置 \(r\) について、次の周期以降の値は

\(kS + P_r\)

ですが、\(S \leq 0\) なので、\(k\) が増えるほど大きくなりません。

つまり、追い付ける可能性があるなら最初の1周期以内だけです。

そのため、\(P_r \geq d\) となる最小の \(r\) を探します。存在しなければ答えは \(-1\) です。

\(S > 0\) の場合

1周期ごとに必ず相対的な進みが \(S\) ずつ増えます。

周期内の各位置 \(r\) について、

\(kS + P_r \geq d\)

となる最小の \(k\) を求めれば、その位置で追い付く最短時刻候補が分かります。

\(P_r \geq d\) なら \(k = 0\) です。

そうでなければ、

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

です。

候補時刻は

\(kN + r\)

なので、全ての \(r = 1, 2, \dots, N\) について調べ、その最小値を答えにします。

アルゴリズム

まず、各 \(i\) について

\(C_i = B_i - A_i\)

を保持します。

各クエリを順に処理します。

クエリ 1 i a b

速さの表の \(i\) 番目を変更するので、

\(C_i = b - a\)

に更新します。

クエリ 2 d

現在の \(C\) に対して、以下を行います。

1. \(S = \sum C_i\) を計算する
2. \(S \leq 0\) の場合
   • 先頭から累積和 \(P_r\) を計算する
   • 初めて \(P_r \geq d\) となる \(r\) があれば、それが答え
   • なければ \(-1\)
3. \(S > 0\) の場合
   • 各 \(r = 1, 2, \dots, N\) について \(P_r\) を計算する
   • 必要な周期数 \(k\) を求める
   • 時刻 \(kN + r\) を候補とする
   • その最小値を出力する

計算量

• 時間計算量: \(O(NQ)\)
  • 更新クエリは \(O(1)\)
  • 質問クエリは \(O(N)\)
  • 制約で \(NQ \leq 10^7\) なので十分間に合います
• 空間計算量: \(O(N)\)

実装のポイント

\(C_i = B_i - A_i\) は負になることがあります。
また、答えの時刻は非常に大きくなる可能性があるため、long long を使います。

\(S > 0\) の場合の切り上げ除算は、

(d - pref + S - 1) / S

で計算できます。

ただし、これは pref < d のときだけ使います。
pref >= d のときは必要な周期数は \(0\) です。

ソースコード

#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;
}

---

この解説は gpt-5.5-xhigh によって生成されました。