The point $$$(x_0 - R, y_0)$$$ always lies on the circle because $$$(x_0 - (x_0 - R))^2 + (y_0 - y_0)^2 = R^2$$$ holds for every $$$R$$$: after expanding the parentheses, we get $$$R^2 = R^2$$$.

#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()

signed main() {
    int tt;
    cin >> tt;
    while (tt --> 0) {
        int x, y, R;
        cin >> x >> y >> R;
        cout << x - R << " " << y << endl;
    }
}

Let us create a boolean array $$$\text{used}$$$ and use it to mark which documents have been printed. For an operation of type 3, we simply set $$$\text{used}_i = 1$$$. Operations of types 1 and 2 are essentially the push and pop operations of a stack. Let us also create a stack $$$\operatorname{memory}$$$. For an operation of type 1, we push the document number onto the stack. For an operation of type 2, we pop the top element and set $$$\text{used}[\operatorname{memory}.\text{top}()] = 1$$$. We should also handle the case when $$$\operatorname{memory}$$$ is empty. Finally, we iterate over the $$$\text{used}$$$ array and output all unmarked elements. The time complexity is $$$O(n)$$$.

#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()

int main() {
    int t;
    cin >> t;
    while (t --> 0) {
        int n;
        string s;
        cin >> n >> s;
        vector<int> stack_;
        vector<bool> used(n);
        for (int i = 0; i < n; ++i) {
            if (s[i] == '1') {
                stack_.push_back(i);
            } else if (s[i] == '2') {
                if (stack_.empty()) {
                    used[i] = true;
                } else {
                    used[stack_.back()] = true;
                    stack_.pop_back();
                }
            } else {
                used[i] = true;
            }
        }
        vector<int> res;
        for (int i = 0; i < n; ++i) {
            if (!used[i]) {
                res.push_back(i + 1);
            }
        }
        cout << res.size() << '\n';
        for (auto &x : res) {
            cout << x << " ";
        }
        cout << '\n';
    }
    return 0;
}

Let $$$f(x) = a_x + a_{x+2} - a_{x+4}$$$ be the value of the triad starting at $$$x$$$. Two triads $$$x \lt y$$$ intersect only if $$$y - x = 2$$$ or $$$y - x = 4$$$. Therefore, the answer is the number of pairs $$$x \lt y$$$ such that $$$f(x) = f(y)$$$, minus the pairs satisfying the same equality for which $$$y - x \in {2, 4}$$$.

We process $$$y$$$ from left to right and use a map to store how many times each value of $$$f$$$ has occurred. We add the number of previous occurrences of $$$f(y)$$$ to the answer. Then we separately subtract $$$1$$$ if $$$f(y - 2) = f(y)$$$ and another $$$1$$$ if $$$f(y - 4) = f(y)$$$: these pairs have just been counted, but their triads intersect. The answer can be as large as $$$\sim 2\cdot10^{10}$$$, so a 64-bit integer type (long long) is required.

The time complexity is $$$O(n \log n)$$$ due to the use of a map.

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(), x.end()

signed main() {
    int tt;
    cin >> tt;
    while (tt --> 0) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (auto &x : a) cin >> x;
        vector<int> arr;
        map<int, int> mp;
        int ans = 0;
        for (int i = 0; i < n - 4; i++) {
            int cur = a[i] + a[i + 2] - a[i + 4];
            ans += mp[cur];
            if (i >= 2 && arr[i - 2] == cur) ans--;
            if (i >= 4 && arr[i - 4] == cur) ans--;
            mp[cur]++;
            arr.push_back(cur);
        }
        cout << ans << endl;
    }
}

There are formally three cases:

• $$$a_i = b_i = c_i$$$: the triple does not change, so the answer cannot become greater than $$$a_i + b_i + c_i$$$;
• $$$a_i \le b_i \le c_i$$$: to leave this state, we have to use operations that decrease some elements (more details below);
• $$$a_i \gt b_i \ \lor \ a_i \gt c_i \ \lor \ b_i \gt c_i$$$: we can simply keep increasing the sum indefinitely because only the third element changes, while the other two remain unchanged.

What should we do in a state with $$$a_i \le b_i \le c_i$$$?

We need to obtain either $$$c_i = b_i - 1$$$ or $$$b_i = a_i - 1$$$. After that, we can increase the sum indefinitely.

Therefore, in this case, the cost of increasing $$$S = a_i + b_i + c_i$$$ to $$$m$$$ can be written as

where $$$e = \min(b-a,c-b)+1$$$.

This function is monotonic, so we can binary-search the answer while handling all triples with $$$a_i = b_i = c_i$$$ separately. The time complexity is $$$O(n \log k)$$$.

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

signed main() {
    int t;
    cin >> t;
    while (t --> 0) {
        int n;
        int k;
        cin >> n >> k;

        vector<int> S(n), E(n);
        vector<int> dead(n);

        const int BIG = numeric_limits<int>::max() / 4;
        int lo = BIG, cap = BIG;

        vector<int> A(n), B(n), C(n);
        for (int i = 0; i < n; i++) cin >> A[i] >> B[i] >> C[i];

        for (int i = 0; i < n; i++) {
            int a = A[i], b = B[i], c = C[i];
            S[i] = a + b + c;
            dead[i] = (a == b && b == c);
            E[i] = (a <= b && b <= c) ? min(b - a, c - b) + 1 : 0LL;
            lo = min(lo, S[i]);
            if (dead[i]) cap = min(cap, S[i]);
        }

        int hi = min(cap, lo + k) + 1;

        auto is_ok = [&](int m){
            int total = 0;
            for (int i = 0; i < n; i++) {
                if (S[i] >= m) continue;
                if (dead[i]) return 0;
                total += (m - S[i]) + 2 * E[i];
                if (total > k) return 0;
            }
            return 1;
        };

        while (hi - lo > 1) {
            int mid = (hi + lo) / 2;
            if (is_ok(mid)) lo = mid;
            else hi = mid;
        }
        cout << lo << '\n';
    }
}

The roads connect only buildings on opposite sides, so the route alternates between the two sides, uses exactly $$$2n - 1$$$ roads, and has length $$$2n - 1 + (\text{the number of roads connecting buildings of the same company})$$$. Let us determine which routes are possible. Suppose K1o0n is at $$$a_k$$$, and all columns to the left have already been visited. If he moves to $$$b_k$$$, the only remaining move from there is to $$$a_{k+1}$$$, and we reach the same situation in column $$$k+1$$$. If instead he moves diagonally to $$$b_{k+1}$$$, then the only remaining unvisited neighbor of $$$b_k$$$ is $$$a_{k+1}$$$, so $$$b_k$$$ must be an endpoint of the route. From this point on, the entire route is forced: first, follow the zigzag $$$a_k \to b_{k+1} \to a_{k+2} \to \ldots$$$ to the end, cross to the other side using the road $$$a_n-b_n$$$, and then follow the second zigzag back to $$$b_k$$$. Therefore, every route is determined by a single number $$$k$$$: first, it follows the “snake” $$$a_1 \to b_1 \to a_2 \to \ldots \to b_{k-1} \to a_k$$$, and then forms a loop to the end and back.

There are $$$n$$$ possible routes in total. We first calculate the length for $$$k=1$$$ (two zigzags and the road $$$a_n-b_n$$$). Moving from $$$k$$$ to $$$k+1$$$ replaces exactly one road: $$$a_k-b_{k+1}$$$ is replaced with $$$a_k-b_k$$$. Thus, we can obtain the length of each next route from the previous one in $$$O(1)$$$ time and take the maximum. The total time complexity is $$$O(n)$$$.

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

signed main() {
    auto f = [](int x, int y) {
        return 1 + (x == y);
    };
    int tt;
    cin >> tt;
    while (tt --> 0) {
        int n;
        cin >> n;
    
        vector<int> a(n), b(n);
        for (auto &x : a) cin >> x;
        for (auto &x : b) cin >> x;
    
        int current = f(a.back(), b.back());
        for (int i = 0; i + 1 < n; i++) {
            current += f(a[i + 1], b[i]);
            current += f(a[i], b[i + 1]);
        }
    
        int answer = current;
    
        for (int i = 0; i + 1 < n; i++) {
            current -= f(a[i], b[i + 1]);
            current += f(a[i], b[i]);
            answer = max(answer, current);
        }
    
        cout << answer << '\n';
    }
}

Let us determine when a number $$$x$$$ has an odd number of divisors. Consider its prime factorization $$$x = p_1^{d_1} p_2^{d_2} \ldots p_k^{d_k}$$$. The number of divisors is $$$\prod (d_i + 1)$$$. For it to be odd, every factor must be odd, which means that every exponent $$$d_i$$$ must be even. $$$F(i, j)$$$ is the product of two values, and every prime occurs in it with an even exponent if and only if the sets of primes occurring with odd exponents in the two factors are equal. For every prefix, we will store the set of primes that occur in its product with odd exponents.

Note that we do not have to store all such sets. If a set contains more than $$$7$$$ primes, their product is guaranteed to be greater than any $$$a_i$$$, while a single spoonful would have to contain all of them at once. Therefore, such a prefix cannot be turned into a perfect square using any single $$$a_i$$$. Thus, we maintain a map only for suitable sets rather than for all of them. The answer is then the sum, over all $$$a_i$$$, of the number of prefixes whose set of primes with odd exponents is equal to that of $$$a_i$$$. The time complexity is $$$O(n \log (7n))$$$; here, the constant $$$7$$$ denotes the maximum possible number of distinct prime divisors of a number not exceeding $$$10^6$$$.

#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()

signed main() {
    vector<int> primes;
    vector<bool> is_prime(32000 + 1, 1);
    is_prime[0] = is_prime[1] = 0;
    for (int i = 2; i <= 32000; i++) {
        if (is_prime[i]) {
            primes.push_back(i);
            for (int j = i * i; j <= 32000; j += i) {
                is_prime[j] = 0;
            }
        }
    }

    int t;
    cin >> t;
    while (t --> 0) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (auto &x : a) cin >> x;

        vector<vector<int>> ker(n);
        for (int i = 0; i < n; i++) {
            int x = a[i];
            for (int j = 0; j < primes.size() && primes[j] * primes[j] <= x; j++) {
                if (x % primes[j] == 0) {
                    int e = 0;
                    while (x % primes[j] == 0) { x /= primes[j]; e++; }
                    if (e & 1) ker[i].push_back(primes[j]);
                }
            }
            if (x > 1) ker[i].push_back(x);
        }

        map<vector<int>, int> mp;
        set<int> odd;
        for (int i = 0; i < n; i++) {
            for (int p : ker[i])
                if (!odd.insert(p).second) odd.erase(p);
            if (odd.size() <= 7)
                mp[vector<int>(all(odd))]++;
        }

        long long ans = 0;
        for (int i = 0; i < n; i++) {
            auto it = mp.find(ker[i]);
            if (it != mp.end()) ans += it->second;
        }
        cout << ans << "\n";
    }
}

First, let us determine which cables should be kept. Suppose that $$$r$$$ old cables remain in the end and form a forest. Then the forest has $$$n-r$$$ connected components, so the crew will have to install $$$n-r-1$$$ new cables. We sell everything that we do not keep. Therefore, for a fixed $$$r$$$, it is optimal to keep the cheapest $$$r$$$ cables that still form a forest. These are exactly the first $$$r$$$ edges selected by Kruskal's algorithm, that is, the $$$r$$$ cheapest edges of the minimum spanning forest.

This gives us the solution. For each connected component, construct a minimum spanning tree and immediately sell every edge that does not belong to these trees: keeping such an edge is never useful for any value of $$$x$$$. If there are $$$c$$$ components, connecting them requires $$$c-1$$$ new cables and costs $$$x + 2x + \ldots + (c-1)x = x \cdot \frac{c(c-1)}{2}$$$.

We can then sell some edges of the spanning forest as well, starting with the most expensive ones. Each removed edge splits one component into two, so one additional cable has to be installed: the first such cable costs $$$x \cdot c$$$, the second costs $$$x \cdot (c+1)$$$, and so on. Let the edges of the spanning forest be sorted in non-increasing order: $$$e_1 \ge e_2 \ge \ldots$$$. Removing the $$$i$$$-th edge is beneficial exactly when $$$e_i \gt x \cdot (c+i-1)$$$. The left-hand side decreases while the right-hand side increases, so the beneficial edges form a prefix. For each scenario, we find the length of this prefix using binary search. Prefix sums of $$$e_i$$$ then allow us to calculate the answer in $$$O(1)$$$.

The total time complexity is $$$O(m \log m)$$$ for Kruskal's algorithm and $$$O(\log n)$$$ per scenario. The profit may be negative if there are many components, and the installation costs can reach $$$5 \cdot 10^8 \cdot \frac{10^5 \cdot (10^5-1)}{2} \approx 2.5 \cdot 10^{18}$$$, so a 64-bit integer type is required.

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(), x.end()

struct Dsu {
    vector<int> p, rank_;
    explicit Dsu(int n) : p(n), rank_(n, 0) { iota(p.begin(), p.end(), 0); }
    int find(int x) {
        while (p[x] != x) x = p[x] = p[p[x]];
        return x;
    }
    bool unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;
        if (rank_[a] < rank_[b]) swap(a, b);
        p[b] = a;
        if (rank_[a] == rank_[b]) ++rank_[a];
        return true;
    }
};

signed main() {
    int t;
    cin >> t;
    while (t --> 0) {
        int n, m, q;
        cin >> n >> m >> q;
        vector<array<int, 3>> edges(m); // {d, u, v}
        int total = 0;
        for (int i = 0; i < m; i++) {
            int u, v, d;
            cin >> u >> v >> d;
            edges[i] = {d, u - 1, v - 1};
            total += d;
        }
        sort(edges.begin(), edges.end());

        Dsu dsu(n);
        vector<int> w;
        w.reserve(min(m, n - 1));
        for (auto &e : edges)
            if (dsu.unite(e[1], e[2])) w.push_back(e[0]);
        int top = w.size();
        vector<int> pref(top + 1, 0);
        for (int i = 0; i < top; i++) pref[i + 1] = pref[i] + w[i];

        for (int i = 0; i < q; i++) {
            int x;
            cin >> x;
            int lo = 0, hi = top;
            while (lo < hi) {
                int mid = lo + (hi - lo) / 2;
                if (w[mid] - x * (n - mid - 1) >= 0) hi = mid;
                else lo = mid + 1;
            }
            int k = n - lo - 1;
            int cost = pref[lo] + x * (k * (k + 1) / 2);
            cout << total - cost << " ";
        }
        cout << endl;
    }
}

For the submatrix $$$[lx, ly, rx, ry]$$$, write $$$S^2$$$ as

Let us change the order of summation: we will choose a pair of cells $$$(i,j)$$$ and $$$(x,y)$$$ and consider the contribution of this pair to the total sum. It is equal to

Since only the parity of the exponent matters, this expression is equal to

Let us group the factors:

Notice that only the parity of the minimum and maximum row and column indices matters. Rewriting the expression, we obtain

Let us calculate the sum over pairs of distinct cells $$$(x,y) \lt (i,j)$$$, where pairs are compared lexicographically. We multiply their contribution by $$$2$$$ and then separately add the contribution of pairs consisting of the same cell:

We divide the contribution of pairs of distinct cells into two more cases: $$$i=x$$$ and $$$x \lt i$$$.

Cells in the same row.

We calculate the first contribution separately for each row. We iterate over the row from left to right, maintain the sum of the elements in even-numbered columns, and add this sum multiplied by $$$a_{i,j}$$$ if $$$(n-i)\equiv_2 1$$$.

Cells in different rows.

We calculate the second contribution by processing the rows in increasing order. For an element $$$(i,j)$$$, we separately consider elements from previous rows whose column index is greater than $$$j$$$ and those whose column index is at most $$$j$$$. Depending on this comparison, different parity conditions are imposed on $$$j$$$ and $$$y$$$.

We maintain prefix and suffix sums over cells whose column indices have the required parity in all previous rows. After processing the current row, we calculate these prefix and suffix sums for it and add them to the accumulated sums.

The total time complexity is $$$O(nm)$$$.

Credits: Noobish_Monk

#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
using pii = pair<int, int>;
 
template <uint32_t MOD>
struct ModularInt {
    int x = 0;
 
    ModularInt() {}
 
    ModularInt(int x) : x(x < 0 ? x + MOD : x % MOD) {}
 
    ModularInt(const ModularInt &other) : x(other.x) {}
 
    ModularInt operator+=(const ModularInt &other) {
        x += other.x;
        if (x >= MOD)
            x -= MOD;
        return *this;
    }
 
    ModularInt operator-=(const ModularInt &other) {
        x -= other.x;
        if (x < 0)
            x += MOD;
        return *this;
    }
 
    ModularInt operator*=(const ModularInt &other) {
        x = ((ll)x * other.x) % MOD;
        return *this;
    }
 
    ModularInt power(ll pw) const {
        ModularInt a(*this);
        ModularInt b = 1;
        for (; pw; pw >>= 1, a *= a)
            if (pw & 1)
                b *= a;
        return b;
    }
 
    ModularInt inv() const {
        return power(MOD - 2);
    }
 
    ModularInt operator/=(const ModularInt &other) {
        x = ((ll)x * other.inv().x) % MOD;
        return *this;
    }
 
    bool operator==(const ModularInt &other) {
        return x == other.x;
    }
 
    bool operator!=(const ModularInt &other) {
        return x != other.x;
    }
 
    friend ModularInt operator+(const ModularInt &a, const ModularInt &b) {
        return ModularInt(a) += b;
    }
 
    friend ModularInt operator-(const ModularInt &a, const ModularInt &b) {
        return ModularInt(a) -= b;
    }
 
    friend ModularInt operator*(const ModularInt &a, const ModularInt &b) {
        return ModularInt(a) *= b;
    }
 
    friend ModularInt operator/(const ModularInt &a, const ModularInt &b) {
        return ModularInt(a) /= b;
    }
 
    friend istream& operator>>(istream& in, ModularInt& other) {
        int x;
        in >> x;
        if (x < 0)
            x += MOD;
        x %= MOD;
        other = x;
        return in;
    }
 
    friend ostream& operator<<(ostream& out, const ModularInt& other) {
        return out << other.x;
    }
};
 
const int mod = 1e9 + 7;
using mint = ModularInt<mod>;
 
mint calc_row(const vector<mint> &a) {
    int n = a.size();
    mint ans = 0;
    mint sum = 0;
    for (int i = 0; i < n; i++) {
        if ((n - i) % 2 == 1)
            ans += sum * a[i];
        if (i % 2 == 0)
            sum += a[i];
    }
    return ans;
}
 
inline void solve() {
    int n, m;
    cin >> n >> m;
    vector a(n, vector<mint>(m));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> a[i][j];
    mint ans = 0;
    int sgn = 1;
    if (n % 2 == 1)
        sgn *= -1;
    if (m % 2 == 1)
        sgn *= -1;
    for (int i = 0; i < n; i++)
        if (i % 2 == 0 && (n - i) % 2 == 1)
            ans += calc_row(a[i]);
    vector<mint> psum_min(m), psum_max(m), tmp(m);
    for (int i = 0; i < n; i++) {
        if ((n - i) % 2 == 1) {
            for (int j = 0; j < m - 1; j++)
                if (j % 2 == 0)
                    ans += a[i][j] * psum_max[j + 1];
            for (int j = 0; j < m; j++)
                if ((m - j) % 2 == 1)
                    ans += a[i][j] * psum_min[j];
        }
        if (i % 2 == 0) {
            for (int j = 0; j < m; j++)
                tmp[j] = j % 2 == 0 ? a[i][j] : 0;
            for (int j = 1; j < m; j++)
                tmp[j] += tmp[j - 1];
            for (int j = 0; j < m; j++)
                psum_min[j] += tmp[j];
            for (int j = 0; j < m; j++)
                tmp[j] = (m - j) % 2 == 1 ? a[i][j] : 0;
            for (int j = m - 2; j >= 0; j--)
                tmp[j] += tmp[j + 1];
            for (int j = 0; j < m; j++)
                psum_max[j] += tmp[j];
        }
    }
    ans *= 2;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (i % 2 == 0 && (n - i) % 2 == 1 && j % 2 == 0 && (m - j) % 2 == 1)
                ans += a[i][j] * a[i][j];
    ans *= sgn;
    cout << ans << '\n';
}
 
signed main() {
    cin.tie(nullptr)->sync_with_stdio(0);
    int tt = 1;
    cin >> tt;
    for (int test_id = 1; test_id <= tt; test_id++) {
        solve();
    }
}