Codeforces Round #299 (Div. 2) C. Tavas and Karafs

問題

Problem - C - Codeforces

解法

まずl番目の値がtより大きい場合はどうしようもないので-1を返す。
そうでない時は二分探索する。r番目の数まで0にすることのできる必要十分条件は,s[r] <= tかつsum(s[l], ..., s[r]) <= m*tである。C++の場合オーバーフローに注意(全部10^6で抑えられるのでlong long で足りるが適当にhigh = 10^9とかすると多分死ぬ)。

以下ソースコード

ll A, B, T;

bool ok(int l, int t, int m, ll med) {
    ll L = A+l*B;
    ll R = A+med*B;
    ll num = med-l+1;
    ll sum = (L+R) * num / 2;
    if (sum <= (ll)m * t && R <= t) return true;
    return false;
}

int solve(int l, int t, int m) {
    ll L = A+l*B;
    if (L > t) return -1;
    ll low = l, high = 1e6+7;
    while (high - low > 1) {
        ll med = (high+low) / 2;
        if (ok(l, t, m, med)) {
            low = med;
        } else {
            high = med;
        }
    }
    return low+1;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> A >> B >> T;
    while (T--) {
        int l, t, m;
        cin >> l >> t >> m;
        l--;
        cout << solve(l, t, m) << endl;
    }
    return 0;
}