A. Find The Array

To satisfy the condition that every element in array b is divisible by at least one of its neighbors, the number 1 is universally effective. Therfeore, we can replace certain elements of array a with 1.

The second condition requires minimizing the variance between a and b. The optimal strategy is to compare the sum of elements at odd positions with that at even positions. If the even-position sum is larger, replace all odd positions with 1; otherwise, replace all even positions with 1.

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
typedef pair<i64, i64> PII;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<int> a(n + 1);
        i64 odd_sum = 0, even_sum = 0;
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
            if (i & 1) odd_sum += a[i];
            else even_sum += a[i];
        }
        if (odd_sum < even_sum) {
            for (int i = 1; i <= n; i += 2) a[i] = 1;
        } else {
            for (int i = 2; i <= n; i += 2) a[i] = 1;
        }
        for (int i = 1; i <= n; ++i)
            cout << a[i] << " \n"[i == n];
    }
    return 0;
}

B. Busy Robot

A robot starts at position 0 on a number line. At certain times, it receives a command to move toward a specified coordinate at a speed of 1 unit per second. While moving to the current target, it ignores any new commands. A command is considered successfully executed if the robot reaches the target position (x_i) within the time interval ([t_i, t_{i+1}]). Given a sequence of commands, determine how many are successfully executed.

We maintain the start (st) and end (ed) of the current movement segment, the time (next) when the robot will finish the current command, and the time (last) when the last executed command was received. Iterate through each command:

• If the current time (t_i \ge next), the robot is idle, so we execute this command: set (next = t_i + |pos_i - ed|), (st = ed), (ed = pos_i), (last = i). If (next \le t_{i+1}), increment the answer.
• Otherwise, the robot is still moving. Check whether the robot passes through (x_i) between (t_i) and (t_{i+1}). Compute the robot's position range during this interval and see if (x_i) lies within it.

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
typedef pair<i64, i64> PII;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<i64> t(n + 1), x(n + 1);
        for (int i = 0; i < n; ++i)
            cin >> t[i] >> x[i];
        t[n] = 1e10;
        i64 next = 0, st = 0, ed = 0, last = 0, ans = 0;
        for (int i = 0; i < n; ++i) {
            if (t[i] >= next) {
                next = t[i] + abs(x[i] - ed);
                st = ed;
                ed = x[i];
                last = i;
                if (next <= t[i + 1]) ++ans;
            } else {
                if (st >= ed) {
                    i64 high = st - (t[i] - t[last]);
                    i64 low = max(ed, st - (t[i + 1] - t[last]));
                    if (x[i] >= low && x[i] <= high) ++ans;
                } else {
                    i64 low = st + (t[i] - t[last]);
                    i64 high = min(ed, st + (t[i + 1] - t[last]));
                    if (x[i] >= low && x[i] <= high) ++ans;
                }
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

C. Building a Fence

We have (n) planks, each 1 unit wide and (k) units tall. The ground height under plank (i) is (h_i). The first and last planks must stand on the ground; the bottom of other planks can be at ground height or up to (k-1) units above ground. Adjacent planks must overlap vertically by at least 1 unit. Determine whether a valid fence can be built.

Let (l, r) be the minimum and maximum possible bottom heights for the current plank. For the next plank, the feasible bottom range is ([l - k + 1,; r + k - 1]), clipped by the ground constraint: ([h_i,; h_i + k - 1]). Update (l = \max(l - k + 1, h_i)), (r = \min(r + k - 1, h_i + k - 1)). If at any point (l > r), construction is impossible. Finally, check whether (h_n) lies within ([l, r]) (since the last plank must be on the ground).

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
typedef pair<i64, i64> PII;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int n, k;
        cin >> n >> k;
        vector<int> h(n + 1);
        for (int i = 1; i <= n; ++i) cin >> h[i];
        bool possible = true;
        int low = h[1], high = h[1];
        for (int i = 2; i <= n; ++i) {
            low = max(low - k + 1, h[i]);
            high = min(high + k - 1, h[i] + k - 1);
            if (low > high) {
                possible = false;
                break;
            }
        }
        if (h[n] < low || h[n] > high) possible = false;
        cout << (possible ? "YES\n" : "NO\n");
    }
    return 0;
}

D. Program

Maintain prefix and suffix information to answer queries fast. For each prefix, store the current sum and its minimum and maximum values during the process. For each suffix, store the relative minimum and maximum offsets from 0. Then, for a query that removes substring ([l, r]), combine the prefix up to (l-1) with the suffix from (r+1) (adjusted by the prefix sum), compute the overall min and max, and output the number of distinct values as (\text{max} - \text{min} + 1).

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
typedef pair<i64, i64> PII;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int n, q;
        cin >> n >> q;
        string s;
        cin >> s;
        s = " " + s;
        vector<i64> pref(n + 2), pref_min(n + 2), pref_max(n + 2);
        vector<i64> suff(n + 2), suff_min(n + 2), suff_max(n + 2);
        for (int i = 1; i <= n; ++i) {
            int delta = (s[i] == '+') ? 1 : -1;
            pref[i] = pref[i - 1] + delta;
            pref_min[i] = min(pref_min[i - 1], pref[i]);
            pref_max[i] = max(pref_max[i - 1], pref[i]);
        }
        suff[n + 1] = suff_min[n + 1] = suff_max[n + 1] = 0;
        for (int i = n; i >= 1; --i) {
            int delta = (s[i] == '+') ? 1 : -1;
            suff[i] = suff[i + 1] + delta;
            suff_min[i] = min(0LL, suff_min[i + 1] + delta);
            suff_max[i] = max(0LL, suff_max[i + 1] + delta);
        }
        while (q--) {
            int l, r;
            cin >> l >> r;
            i64 cur_min = 0, cur_max = 0;
            cur_min = min(cur_min, pref_min[l - 1]);
            cur_max = max(cur_max, pref_max[l - 1]);
            i64 base = pref[l - 1];
            cur_min = min(cur_min, suff_min[r + 1] + base);
            cur_max = max(cur_max, suff_max[r + 1] + base);
            cout << cur_max - cur_min + 1 << '\n';
        }
    }
    return 0;
}