This is a classic problem where we can solve the queries offline. First, we receive all the queries, calculate the response for each node, and then respond. To calculate the response for each node, we will perform a DFS starting at vertex $$$1$$$ and create a map where we maintain the frequency of each color along the path from the root to the current node in the DFS. When we enter a new vertex, we add $$$1$$$ to the frequency of the current vertex's color in the map, and when we leave that node, we subtract $$$1$$$ from that color's frequency. Furthermore, we must ensure that all colors in the map have a positive frequency, removing any colors that reach a frequency of $$$0$$$ from the map. Thus, the response for each node will simply be the number of colors in the map after processing that node in the DFS.

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX = 1e5+5;
 
int cor[MAX];
vector<int> g[MAX];
 
int ans[MAX];
 
map<int,int> mp;
 
void dfs(int u, int p) {
    mp[cor[u]]++;
 
    for (auto v : g[u]) if (v != p) {
        dfs(v,u);
    }
 
    ans[u] = mp.size();
 
    mp[cor[u]]--;
 
    if (mp[cor[u]] == 0) {
        mp.erase(cor[u]);
    }
}
 
int main() {
    int n, q; cin >> n >> q;
 
    for (int i = 0; i < n; i++) {
        cin >> cor[i];
    }
 
    for (int i = 1; i < n; i++) {
        int a,b; cin >> a >> b;
        a--; b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
 
    dfs(0,-1);
 
    while (q--) {
        int x; cin >> x;
        x--;
        cout << ans[x] << '\n';
    }
 
}

You only need to implement the operations exactly as they were described. For example, for the operation $$$\operatorname{chmod}(l,r,x)$$$, just iterate over all indices $$$i$$$ in the interval $$$[l,r]$$$ and perform the described operation. Thus, each operation will be performed in $$$\mathcal{O}(n)$$$; therefore, the final complexity of the solution will be $$$\mathcal{O}(nq)$$$. Since $$$1 \leq n,q \leq 1000$$$, this is fast enough.

#include<bits/stdc++.h>
 
using namespace std;
 
int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);
 
	int n,q;cin>>n>>q;
	vector<int> as(n);
	for (auto& a : as) cin>>a;
 
	while(q--) {
		int t; cin>>t;
		if (t==1) {
			int l,r,x;cin>>l>>r>>x; l--; r--;
			for (int i = l; i <= r; i++) as[i] = as[i] % x;
		}
		else if (t==2) {
			int l,r,x;cin>>l>>r>>x; l--; r--;
			for (int i = l; i <= r; i++) as[i] = max(as[i], x);
		} else {
			int l,r;cin>>l>>r; l--; r--;
			int ans = 0;
			for (int i = l; i <= r; i++) ans += as[i];
			cout << ans << '\n';
		}
	}
}

Since the treasure is chosen uniformly at random within the rectangle, the probability that it lies in a given region is proportional to the area of that region.

The team excavates a region in the shape of a regular hexagon with side length $$$l$$$, completely contained within the rectangle. Therefore, the required probability is given by: $$$\frac{\text{Area of the hexagon}}{\text{Area of the rectangle}}.$$$

The area of the rectangle is: $$$A_{r} = b \cdot h.$$$

A regular hexagon can be divided into 6 equilateral triangles of side length $$$l$$$. The area of each triangle is: $$$\frac{\sqrt{3}}{4} \cdot l^2.$$$

Thus, the area of the hexagon is: $$$A_{h} = 6 \cdot \frac{\sqrt{3}}{4} \cdot l^2 = \frac{3\sqrt{3}}{2} \cdot l^2.$$$

Finally, the answer is: $$$\frac{3\sqrt{3}}{2} \cdot \frac{l^2}{b \cdot h}$$$.

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n, m, l;
    cin >> n >> m >> l;
 
    double area_hex = 3.0 * sqrt(3.0) * l * l / 2.0;
    double area_rect = 1.0 * n * m;
 
    double ans = area_hex / area_rect;
 
    cout << fixed << setprecision(10) << ans << '\n';
    return 0;
}

The main point of this problem is the following fact: even with $$$N = 10^{12}$$$, we have a relatively small number of different values of $$$\lfloor N/i \rfloor$$$.

We can divide the values of $$$i$$$ into two groups: $$$i \leq \sqrt{N}$$$ and $$$i \gt \sqrt{N}$$$. In the first group, we have $$$\sqrt{N}$$$ different values for $$$i$$$, so we have at most $$$\sqrt{N}$$$ different values for $$$\lfloor N/i \rfloor$$$. In the second group, we have $$$N/i \lt \sqrt{N}$$$, so we have only $$$\sqrt{N}$$$ possible values for $$$N/i$$$. Therefore, for a given $$$N$$$, there are at most $$$2\sqrt{N}$$$ different values of $$$\lfloor N/i \rfloor$$$.

In other words, for $$$N = 10^{12}$$$, we have at most $$$2\cdot 10^6$$$ values for $$$\lfloor N/i \rfloor$$$.

We can build a segment tree with lazy propagation, in which each position corresponds to a segment of positions $$$i$$$ with the same value of $$$\lfloor N/i \rfloor$$$. It is also necessary to store the actual length of each segment, so that we can compute its real value for sum queries.

The only remaining problem is that the updates and queries may define $$$l$$$ and $$$r$$$ that do not match the beginning and end of the segments we defined, so we apply the sum to only some of the elements. To solve this problem, we must also split our segments at those input positions. This adds at most $$$2 \cdot Q$$$ positions to our segment tree.

Thus, the problem can be solved in $$$O(S \log S)$$$, where $$$S = 2 \cdot ( \sqrt{N} + Q )$$$.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
 
// Lazy Segment Tree Template with MOD Sum
template<class S> struct LazySeg{ // n MUST be a power of 2
	using T = typename S::T; using L = typename S::L;
	int n; vector<T> seg; vector<L> lz; vector<bool> ig;
	LazySeg(int s):n(s),seg(2*n,S::id),lz(2*n),ig(2*n,1){}
	void apply(int p, L v, int l, int r){
		seg[p] = S::ch(seg[p],v,l,r);
		if (r-l>1)lz[p] = ig[p] ? v : S::cmp(lz[p], v), ig[p] = 0;
	}
	void prop(int p, int l, int r){
		if (ig[p])return;
		int m = (l+r)/2; ig[p] = 1;
		apply(2*p, lz[p], l, m);
		apply(2*p+1, lz[p], m, r);
	}
	void update(L v, int l, int r){return update(v,l,r,1,0,n);}
	void update(L v, int lq, int rq, int no, int lx, int rx){
		if (rq <= lx or rx <= lq)return;
		if (lq <= lx and rx <= rq)return apply(no, v, lx, rx);
		int mid = (lx+rx)/2; prop(no,lx,rx); 
		update(v,lq,rq,2*no,lx,mid); update(v,lq,rq,2*no+1,mid,rx);
		seg[no] = S::op(seg[2*no],seg[2*no+1]);
	}
	T query(int l, int r){return query(l,r,1,0,n);}
	T query(int lq, int rq, int no, int lx, int rx){
		if (rq <= lx or rx <= lq)return S::id;
		if (lq <= lx and rx <= rq)return seg[no];
		int mid = (lx+rx)/2; prop(no,lx,rx); 
		return S::op(query(lq,rq,2*no,lx,mid),query(lq,rq,2*no+1,mid,rx));
	}
};
 
constexpr int MOD = 1e9+7;
int add(int a, int b){return a+b < MOD ? a+b : a+b-MOD;}
int mul(int a, int b){return (int)((ll)a*b%MOD);}
 
struct SumRange{
	using T = pair<int, ll>;
	using L = int;
	static constexpr T id = {0, 0};
	static T op(T a, T b){return {add(a.first, b.first), a.second+b.second};}
	static T ch(T a, L b, int l, int r){return {add(a.first, mul(b, a.second%MOD)), a.second};}
	static L cmp(L a, L b){return add(a, b);}
};
 
// End of Lazy Segment Tree Template
 
int main(){
	cin.tie(0)->sync_with_stdio(0);
	ll n; 
	int q; 
	cin >> n >> q;
	vector<ll> cords;
	map<ll, pair<ll, ll>> floors;
	for(ll l = 1, r; l <= n; l = r+1){
		r = n / (n / l);
		floors[n/l] = {l, r};
		cords.push_back(l-1);
		cords.push_back(r);
	}
	vector<tuple<int, ll, ll, int>> qs;
	for(int i = 0; i < q; i++){
		int t; 
		cin >> t;
		ll l, r, k = 0;
		int x = 0; 
		cin >> l >> r;
		if (t == 2){
			cin >> k >> x;
			if (not floors.count(k))continue;
			l = max(l, floors[k].first);
			r = min(r, floors[k].second);
			if (l > r)continue;
		}
		l--;
		cords.push_back(l);
		cords.push_back(r);
		qs.emplace_back(t, l, r, x);
	}
	sort(cords.begin(), cords.end());
	cords.erase(unique(cords.begin(), cords.end()), cords.end());
	int m = 1, cs = (int)cords.size();
	while(m < cs)m *= 2;
	LazySeg<SumRange> seg(m);
	for(int i = 0; i < cs; i++)seg.seg[i+m].second = (i == cs-1 ? n+1 : cords[i+1]) - cords[i];
	for(int i = m-1; i > 0; i--)seg.seg[i].second = seg.seg[2*i].second + seg.seg[2*i+1].second;
	for(auto [t, l, r, x] : qs){
		int cl = lower_bound(cords.begin(), cords.end(), l) - cords.begin();
		int cr = lower_bound(cords.begin(), cords.end(), r) - cords.begin();
		if (t == 1)cout << seg.query(cl, cr).first << '\n';
		else seg.update(x, cl, cr);
	}
}

This problem is indeed "EZ". The snake should always eat the heaviest available mouse, that is, the mice weighing $$$N$$$, $$$N-2$$$, $$$N-4$$$... The sum of these values can be calculated with a simple loop, in $$$O(N)$$$, or with a mathematical calculation, in $$$O(1)$$$.

#include<bits/stdc++.h>
using namespace std;
 
int main(){
    int n, ans = 0; cin >> n;
    for(; n > 0; n -= 2)ans += n;
    cout << ans << endl;
}

For $$$A(x) \cdot C(x) = B(x)$$$, it is necessary that $$$C(x) = x^k$$$, for some non-negative integer $$$k$$$. That is, the set $$$P$$$ must be equal to the set of values of $$$S$$$ summed by $$$k$$$. Thus, the answer to the problem can be calculated by iterating through all $$$k$$$ from $$$0$$$ to $$$N-1$$$ and summing the number of ways to choose $$$S$$$ such that $$$S' = P$$$, where $$$S'$$$ is the set of values of $$$S$$$ summed by $$$k$$$.

To aid in this process, we can transform the problem into choosing $$$S$$$ such that $$$S = P$$$, with $$$S$$$ being a set of values from the list $$$L'$$$, in which $$$L'_i = L_i + k$$$. This is the same as a set of positions of $$$L'$$$, which is the same as the set of values of those positions. We will call such sets $$$S$$$ valid, and we need to count their quantity.

Consider the functional graph induced by $$$L'$$$, where $$$i$$$ has an edge to $$$min(N+1, L'_i)$$$ and $$$N+1$$$ has an edge to itself. The structure of this graph is similar to a permutation graph, which has only disjoint cycles, except that there is a single component with a tree structure rooted at $$$N+1$$$.

By the condition for a $$$S$$$ to be valid, if $$$i$$$ is in $$$S$$$, then $$$L'_i$$$ would also need to be there. By induction, we can see that if $$$i$$$ is in $$$S$$$, then every component of $$$i$$$ in the induced functional graph would need to be in $$$S$$$. But $$$N+1$$$ cannot be there, as it is an invalid position in the list $$$L'$$$. Therefore, the valid sets $$$S$$$ are only the unions of the cycles of the induced functional graph. If there are $$$x$$$ cycles, the number of valid sets is $$$2^x-1$$$.

The number of cycles can be calculated in $$$O(N)$$$ to be added to the total answer. The final complexity of the solution, due to iteration of $$$k$$$, is $$$O(N^2)$$$.

#include<bits/stdc++.h>
using namespace std;
 
constexpr int MOD = 998244353;
 
int main(){
	int n; cin >> n;
	vector p(n, 0);
	for(int& x : p)cin >> x, x--;
	int ans = 0;
	vector vis(n, 0);
	for(int k = 0; k < n; k++){
		for(int i = 0; i < n; i++)vis[i] = p[i] < 0;
		int q2 = 1;
		for(int i = 0; i < n; i++){
			if (vis[i])continue;
			int cur = i;
			for(; cur < n and not vis[cur]; cur = p[cur])vis[cur] = 1;
			if (cur == i)q2 = q2 * 2 % MOD;
		}
		ans = (ans + q2 - 1) % MOD;
		for(int i = 0; i < n; i++)p[i]++;
	}
	cout << ans << endl;
}

For each team, we are given four integers $$$(a_i, b_i, c_i, d_i)$$$. Observe that after the two stages, the number of remaining participants is $$$|a_i - b_i|$$$ and $$$|c_i - d_i|$$$. Define a vector for each team:

If we choose a subset $$$S$$$, let $$$(X, Y) = \sum_{i \in S} p_i$$$. For a query $$$(k, l)$$$, the penalty is:

We use the identity:

Thus, we can consider four directions $$$d = (\pm k, \pm l)$$$ and compute:

We want to maximize:

This is maximized by taking all indices such that:

So the subset with the largest value consists exactly of all points lying in the half-plane defined by $$$d$$$.

We simulate this process by inserting all points and all query directions (four per query), and sorting them by angle.

We process everything in circular order using two pointers to maintain a window that contains exactly the points with $$$p_i \cdot d \ge 0$$$.

To compute the sum efficiently, we maintain prefix sums of the points.

Complexity: $$$O((n+q)\log(n+q))$$$.

Be careful with the point $$$(0, 0)$$$ during angular sorting.

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
 
struct point{
    int x, y;
    int id;
 
    point(int _x=0, int _y=0){
        x = _x, y = _y;
        id = -1;
    }
 
    point operator +(point b){
        return {x + b.x, y + b.y};
    }
 
    point operator -(point b){
        return {x - b.x, y - b.y};
    }
 
    int operator *(point b){
        return x*b.x + y*b.y;
    }
 
    int operator ^(point b){
        return x*b.y - y*b.x;
    }
 
    int cross(point b, point c){
        return (b - *this) ^ (c - *this);
    }
 
    bool operator <(point &b){
        return make_pair(x, y) < make_pair(b.x, b.y);
    }
 
};
 
int ret[2][2] = {{2, 1}, {3, 0}};
int quad(point p) { 
    return ret[p.x>=0][p.y>=0];  
}
 
bool cmp(point a, point b){
    point v_a = a, v_b = b;
    if(quad(v_a) == quad(v_b)){
        if((v_a^v_b) == 0LL){
            return (v_a*v_a) < (v_b*v_b);
        }
        return (v_a^v_b) > 0LL;
    }
    return quad(v_a) < quad(v_b);
}
 
int32_t main(){
 
    int n, q;
    cin >> n >> q;
 
    vector<point> pts;
    for(int i=0; i<n; i++){
        int a, b, c, d;
        cin >> a >> b >> c >> d;
 
        if(a != b or c != d){
            pts.push_back({a - b, c - d});
        }
    }
    n = pts.size();
 
    vector<point> queries;
    for(int i=0; i<q; i++){
        point qi;
        cin >> qi.x >> qi.y;
 
        if(qi.x == 0 and qi.y == 0){
            continue;
        }
 
        qi.id = i;
        for(int s1 : {1, -1}){
            for(int s2 : {1, -1}){
                point aux = qi;
                aux.x = s1 * aux.x;
                aux.y = s2 * aux.y;
 
                queries.push_back(aux);
            }
        }
    }
    if(queries.size() == 0){
        for(int i=0; i<q; i++){
            cout << 0 << '\n';
        }
        return 0;
    }
 
    for(auto qi : queries){
        pts.push_back(qi);
    }
    n = pts.size();
 
    sort(pts.begin(), pts.end(), cmp);
 
    for(int rep=0; rep<2; rep++){
        for(int i=0; i<n; i++){
            pts.push_back(pts[i]);
        }
    }
    vector<point> psum(3*n);
    if(pts[0].id == -1){
        psum[0] = pts[0];
    }
    for(int i=1; i<3*n; i++){
        psum[i] = psum[i-1];
        if(pts[i].id == -1){
            psum[i] = psum[i-1] + pts[i];
        }
    }
 
    int l = n-1, r = n;
    while(pts[l] * pts[n] >= 0 and (pts[l] ^ pts[n]) > 0){
        l--;
    }
 
    vector<int> ans(q, 0);
    for(int i=n; i<2*n; i++){
        while(r < 3*n and pts[r] * pts[i] >= 0 and (pts[i] ^ pts[r]) >= 0){
            r++;
        }
 
        while(pts[l] * pts[i] < 0 or (pts[l] ^ pts[i]) < 0){
            l++;
        }
 
        point p = psum[r-1];
        if(l != 0){
            p = p - psum[l-1];
        }
 
        if(pts[i].id == -1){
            continue;
        }
        point qi = pts[i];
 
        ans[qi.id] = max(ans[qi.id], qi * p);
    }
 
    for(int i=0; i<q; i++){
        cout << ans[i] << '\n';
    }
 
    return 0;
}

For $$$X$$$ to divide $$$A$$$, the exponent of each prime in the factorization of $$$X$$$ must be less than or equal to its exponent in the factorization of $$$A$$$. When we multiply $$$A$$$ by $$$X$$$, we add the exponents from the factorization of $$$X$$$ to the exponents in the factorization of $$$A$$$. When we raise $$$A$$$ to the power of $$$X$$$, we multiply each exponent in the factorization of $$$A$$$ by $$$X$$$.

We can store a list of the exponents in the factorization of $$$A$$$ (initially consisting only of $$$0$$$'s) and update it according to queries of types 1 and 2.

Queries of type 1 can be processed quickly if we know the factorization of $$$X$$$, since a number up to $$$10^5$$$ is divisible by at most 6 distinct primes and only those will have their exponents modified.

Similarly, queries of type 3 can be processed quickly if we only check the exponents of the primes that divide $$$X$$$.

For queries of type 2, we need to multiply the exponent values of all primes, which would result in TLE for many queries of this type. But numbers up to $$$10^5$$$ have small exponents in their factorizations (the maximum exponent for the factor $$$2$$$, for example, is $$$16$$$). We can then maintain a set containing only the primes whose exponents are nonzero and smaller than their maximums, and update only the exponents of those primes. Since each prime can only be processed by queries of type 2 at most 4 times before being removed from this set, these queries are processed quickly.

#include<bits/stdc++.h>
using namespace std;
 
signed main(int argc, char *argv[]){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int Q; cin >> Q;
    vector<pair<int, int>> queries(Q);
    for(auto &[t, X] : queries) cin >> t >> X;
 
 
    const int MAXX = 100000;
    vector<int> lp(MAXX + 1);
    vector<int> primes;
    for(int i = 2; i <= MAXX; i++){
        if(lp[i] == 0){
            lp[i] = i;
            primes.push_back(i);
        }
        for(int p : primes){
            if(p > lp[i] || i * p > MAXX) break;
            lp[i * p] = p;
        }
    }
 
    auto factorize = [&](int x) -> vector<pair<int, int>>{
        vector<pair<int, int>> ret;
        while(x != 1){
            if(ret.empty() || ret.back().first != lp[x])
                ret.push_back({lp[x], 0});
            ret.back().second++;
            x /= lp[x];
        }
        return ret;
    };
 
    vector<int> lim(MAXX + 1);
    for(int i = 2; i <= MAXX; i++){
        if(lp[i] == i){
            int cur = 1;
            while((long long)cur * i <= MAXX)
                lim[i]++, cur *= i;
        }
    }
 
    vector<int> exp(MAXX + 1);
    set<int> small;
    for(auto [t, X] : queries){
        if(t == 1){
            for(auto [p, e] : factorize(X)){
                if(exp[p] == 0)
                    small.insert(p);
                exp[p] += e;
                if(exp[p] >= lim[p])
                    exp[p] = lim[p], small.erase(p);
            }
        }else if(t == 2){
            vector<int> erase;
            for(int p : small){
                exp[p] *= X;
                if(exp[p] >= lim[p])
                    exp[p] = lim[p], erase.push_back(p);
            }
            for(int p : erase)
                small.erase(p);
        }else if(t == 3){
            bool ok = true;
            for(auto [p, e] : factorize(X))
                ok &= (e <= exp[p]);
            if(ok) cout << "Yes\n";
            else cout << "No\n";
        }
    }
}

The statement guarantees that the test cases will have randomly generated $$$N$$$ and $$$V$$$. Therefore, for a given subsequence $$$A$$$ of the vector, we can consider that its hash $$$H(A)$$$ is also a random result, as is the hash $$$H(A^c)$$$ of its complement.

Let $$$M = 998244353$$$ (the modulus). There are $$$M^2$$$ possible values for the pair $$$(H(A), H(A^c))$$$, and in exactly $$$\dfrac{M \cdot (M-1)}{2}$$$ of them, $$$H(A)$$$ is less than $$$H(A^c)$$$, these being the ones that result in $$$A$$$ satisfying the condition. Considering that all these pairs are equally likely due to randomness, we have a probability of $$$\dfrac{M \cdot (M-1)}{2 \cdot M^2}$$$ of any subsequence $$$A$$$ satisfying the condition. Since $$$M$$$ is large, this is extremely close to $$$\dfrac{1}{2}$$$, therefore we will consider this probability in our calculations from now on.

Since the probability of any subsequence meeting the condition is practically $$$\dfrac{1}{2}$$$, the probability of not meeting it can also be estimated as $$$\dfrac{1}{2}$$$. Thus, the probability of the $$$i$$$-th smallest lexicographical subsequence being the answer to be printed is $$$\dfrac{1}{2^i}$$$, because this requires that all previous ones do not meet the condition and it meets it. As this probability becomes exponentially small as $$$i$$$ grows, we can see that we can manually test a few subsequences among the lexicographically smallest until we find an answer.

The problem then becomes iterating through the subsequences of the vector in lexicographical order and testing each one manually. To facilitate this process, we can make an additional assumption that the subsequence that is the answer will contain few elements---estimating that the probability of containing exactly $$$k$$$ elements is $$$\dfrac{1}{2^k}$$$ or worse, since there are at least $$$k$$$ lexicographically smaller subsequences (their prefixes). Thus, we can iterate through the subsequences of size $$$k$$$ in lexicographical order, for every $$$k$$$ down to a small value (for example, $$$20$$$), until we find one that meets the condition (which should happen quickly). A well-known way to perform this iteration is using a recursive function.

Finally, among the fixed-size subsequences we find (the lexicographically smallest within their size), we choose the lexicographically smallest one as the answer. Therefore, the probability of the answer not being one of those we tested is worse than $$$\dfrac{1}{2^K}$$$, where $$$K$$$ is the largest value of $$$k$$$ tested. Furthermore, the probability of the iteration for a fixed size testing more than $$$i$$$ subsequences is close to $$$\dfrac{1}{2^i}$$$, which shows that the algorithm should run in near-linear time for each $$$k$$$, mainly due to the computational cost of calculating the hashes for the condition verification. With this, we can be confident that the solution will prove correct and efficient enough for randomly generated test cases.

#include<bits/stdc++.h>
using namespace std;
 
#define ll long long
constexpr int P = 100019;
constexpr int M = 998244353;
int add(int a, int b){return a+b < M ? a+b : a+b-M;}
int mul(int a, int b){return (int)((ll)a*b%M);}
 
int main(){
	cin.tie(0)->sync_with_stdio(0);
	int n; cin >> n;
	vector v(n, 0), pw(n+1, 1);
	for(int i = 1; i <= n; i++)pw[i] = mul(pw[i-1], P);
	for(int& x : v)cin >> x;
	int mx = *max_element(v.begin(), v.end()) + 1;
	vector<vector<int>> pos(mx);
	for(int i = 0; i < n; i++)pos[v[i]].push_back(i);
	auto H = [&](vector<int>& x){
		int res = 0;
		for(int i = 0; i < (int)x.size(); i++)res = add(res, mul(x[i], pw[n-i]));
		return res;
	};
	vector<int> cur, idx;
	auto test = [&](){
		if (cur.empty())return false;
		vector<int> comp;
		for(int i = 0; i < (int)idx.size(); i++){
			int l = i ? idx[i-1] : -1, r = idx[i];
			for(int j = l+1; j < r; j++)comp.push_back(v[j]);
		}
		for(int j = idx.back()+1; j < n; j++)comp.push_back(v[j]);
		return H(cur) < H(comp);
	};
	vector<vector<int>> ans;
	auto brute = [&](auto rec, int l, const unsigned s)->bool{
		if (cur.size() == s)if (test())return ans.push_back(cur), true;
		if (cur.size() > s or l >= n)return false;
		for(int x = 0; x < mx; x++){
			for(auto it = lower_bound(pos[x].begin(), pos[x].end(), l); it != pos[x].end(); it++){
				int p = *it;
				cur.push_back(x);
				idx.push_back(p);
				bool res = rec(rec, p+1, s);
				cur.pop_back();
				idx.pop_back();
				if (res)return true;
			}
		}
		return false;
	};
	for(int i = 1; i <= 10; i++)brute(brute, 0, i);
	sort(ans.begin(), ans.end());
	for(int x : ans[0])cout << x << ' ';
	cout << '\n';
}

Arthur must choose all prime numbers up to $$$N$$$ as the values for $$$X$$$ so that he does not have dinner at the RU on any of the $$$N$$$ days.

Clearly, every prime number up to $$$N$$$ must be chosen, because prime numbers are only multiples of $$$1$$$ and themselves. Furthermore, every non-prime number is a multiple of some prime number, so by choosing all primes, Arthur will indeed not have dinner at the RU on any of the $$$N$$$ days. Using any non-prime number as the value of $$$X$$$ would be redundant, which shows that this is the minimum possible answer.

To count how many prime numbers exist up to $$$N$$$, we can use the Sieve of Eratosthenes algorithm:

Initialize an array $$$P$$$ with $$$N$$$ positions, initially all equal to $$$1$$$. Now, we iterate through all the numbers $$$i$$$ from $$$2$$$ to $$$N$$$. If $$$P_i = 0$$$, then $$$i$$$ is not prime. Otherwise, $$$i$$$ is prime, and the answer is incremented. Furthermore, if this is the case, we iterate through the multiples $$$j$$$ of $$$i$$$ up to $$$N$$$, marking $$$P_j = 0$$$, so that in subsequent iterations we do not fail to consider them as non-prime.

The complexity of this algorithm is $$$O(N log(log(N)))$$$. A more complete explanation can be found at: https://cp-algorithms.com/algebra/sieve-of-eratosthenes.html.

#include<bits/stdc++.h>
using namespace std;
 
int main(){
	int n; cin >> n;
	int ans = 0;
	vector taken(n+1, 0);
	for(int i = 2; i <= n; i++){
		if (not taken[i])ans++;
		else continue;
		for(int j = i; j <= n; j+=i)taken[j] = 1;
	}
	cout << ans << endl;
}

This problem can be implemented with conditionals: we can check whether $$$(T_a, T_d)$$$ falls into the first case of the definition of $$$M$$$ or not, and multiply the power $$$P$$$ by $$$2$$$ or $$$\dfrac{1}{2}$$$ accordingly. Then we compute $$$X = max(0, H-P)$$$ (with $$$P$$$ already multiplied). After that, if $$$X = 0$$$, print "Nocaute!"; otherwise, print the other message.

#include<bits/stdc++.h>
using namespace std;
 
int main(){
	string ta, tb;
	int p, h;
	cin >> ta >> tb >> p >> h;
	if (ta == "F" and tb == "G")p *= 2;
	else if (ta == "G" and tb == "W")p *= 2;
	else if (ta == "W" and tb == "F")p *= 2;
	else p /= 2;
	h = max(0, h - p);
	if (h)cout << "Sobraram " << h << " pontos de vida!";
	else cout << "Nocaute!";
	cout << '\n';
}

Let $$$L$$$ be the list representing the song lyrics, with $$$L_i$$$ being the string representing the $$$i$$$-th verse. Let $$$N$$$ be the size of $$$L$$$. Let $$$K$$$ be the maximum size of a string in $$$L$$$.

We can build the Suffix Automaton of this list. This can be done using the usual automaton construction algorithm, considering the list $$$L$$$ as a string whose alphabet consists of words of up to $$$K$$$ letters, in $$$O(N K \log N)$$$. From the automaton, we can use its suffix-link tree to find the Echo Segments of the lyrics.

To do this, we will iterate over the equivalence classes of $$$L$$$ and process their complete $$$endpos$$$ set (positions where an occurrence of a string from the class ends) using the Small to Large technique. This reduces the problem to: updating the answer considering one position from the $$$endpos$$$ of this class based on the current state of the set (a process called query), and updating the state of the set based on a new $$$endpos$$$ position of this class (a process called update).

Consider a class that has one occurrence ending at $$$r2$$$ and another ending at $$$r1$$$ ($$$r2 \gt r1$$$). Let $$$s = r2 - r1$$$. If $$$s$$$ is less than or equal to the maximum length of the class, then there exists a sublist of $$$L$$$ ending at $$$r2$$$ with size $$$2 \cdot s$$$ that is an Echo Segment. Thus, the value of this Echo Segment would be $$$(2 \cdot s) \cdot \sum_{k=r1-s+1}^{r2} |L_k| = (2 \cdot s) \cdot 2 \cdot \sum_{k=r1+1}^{r2} |L_k| = 4 \cdot (s) \cdot \sum_{k=r1+1}^{r2} |L_k|$$$.

To help with this, consider the vector $$$P$$$ such that $$$P_i = \sum_{k=1}^i |L_k|$$$. Then the formula can be written as $$$4 \cdot (s) \cdot (P_{r2} - P_{r1}) = 4 \cdot (r2 - r1) \cdot (P_{r2} - P_{r1})$$$. An even more convenient form is $$$4 \cdot (r2 \cdot P_{r2} - r2 \cdot P_{r1} - r1 \cdot P_{r2} + r1 \cdot P_{r1})$$$. This makes it possible to see that, for a certain $$$r2$$$, it is enough to know, for every $$$r1$$$ present in the $$$endpos$$$ from $$$r2 - M$$$ to $$$r2$$$ (where $$$M$$$ is the maximum length of the class), the number of such $$$r1$$$s, their sum, the sum of their $$$P_{r1}$$$, and the sum of $$$r1 \cdot P_{r1}$$$. The analysis for $$$r1$$$ is analogous.

Thus, we will maintain structures to compute and update these interval sums quickly — for example, four instances of a BIT / Fenwick Tree. Then the update process is reduced to BIT updates. In the query, it is enough to consider the current position as $$$r1$$$ and $$$r2$$$ and check its contribution to the total answer. Since each operation on a BIT takes $$$\log N$$$, the total complexity of this process is $$$O(N \log^2 N)$$$.

The total complexity of the solution is $$$O(N K \log N + N \log^2 N)$$$, which comfortably fits within the time limit.

#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
// BIT Template
 
#define sz(x) (int)x.size()
#define chf(a, f, b) a = f(a, b)
template<class S>
struct BIT{
	using T = typename S::T;
	int n; vector<T> bit;
	int lb(int x){return x&(-x);}
	BIT(int s):n(s),bit(1+n,S::id){}
	void add(T x, int p){for(p++;p<=n;p+=lb(p))chf(bit[p],S::op,x);}
	T query(int l, int r){
		T lv=S::id, rv=S::id; r++;
		for(;r>=1;r-=lb(r))chf(rv,S::op,bit[r]);
		for(;l>=1;l-=lb(l))chf(lv,S::op,bit[l]);
		return S::op(rv,S::inv(lv));
	}
};
 
struct SumGroup{
	using T = ll;
	static constexpr T id = 0;
	static T op(T a, T b){return a+b;}
	static T inv(T a){return -a;}
};
 
// End of BIT Template
 
 
// Suffix Automaton Template
 
#define pb push_back
template<class C, class G> struct Automaton{
	vector<G> dag; 
	vector<int> lnk, len, pos;
	int last, t;
	template<class S> Automaton(S& str):dag(2),lnk(2,0),len(2,0),pos(2,0),last(1),t(1){for(C& c : str)add(c);}
	int new_node(int l, int d){dag.pb(G()); lnk.pb(0); len.pb(l), pos.pb(d); return sz(dag)-1;}
	void add(C& c){
		int cur = new_node(len[last]+1, t++), p = last;
		while(p and not dag[p][c])dag[p][c] = cur, p = lnk[p];
		if (not p)lnk[cur] = 1;
		else {
			int q = dag[p][c];
			if (len[p]+1 == len[q])lnk[cur] = q;
			else{
				int clone = new_node(len[p]+1, 0);
				dag[clone] = dag[q];
				lnk[clone] = lnk[q];
				lnk[q] = lnk[cur] = clone;
				while(p and dag[p][c] == q)dag[p][c] = clone, p = lnk[p];
			}
		}
		last = cur;
	}
};
 
// End of Suffix Automaton Template
 
int main(){
	cin.tie(0)->sync_with_stdio(0);
	int n; cin >> n;
	vector<string> mus(n);
	for(string& v : mus)cin >> v;
	
	vector lens(n+1, 0);
	for(int i = 0; i < n; i++)lens[i+1] = (int)mus[i].size();
	partial_sum(lens.begin(), lens.end(), lens.begin());
	
	Automaton<string, map<string, int>> aut(mus);
	const auto& epos = aut.pos;
	const auto& clen = aut.len;
	const auto& alnk = aut.lnk;
	
	int s = sz(alnk);
	vector<vector<int>> g(s);
	for(int i = 1; i < s; i++)g[alnk[i]].push_back(i);
	vector big(s, -1), sub(s, 1), pos(s, 0), pre(0, 0);
	auto dfspre = [&](auto rec, int v)->void {
		pos[v] = (int)pre.size();
		pre.push_back(v);
		for(int f : g[v]){
			rec(rec, f);
			sub[v] += sub[f];
			if (big[v] == -1 or sub[f] > sub[big[v]])big[v] = f;
		}
	};
	dfspre(dfspre, 1);
	
	BIT<SumGroup> bit_has(n+1), bit_pos(n+1), bit_psum(n+1), bit_prod(n+1);
	auto update = [&](int i, int mul){
		int p = epos[i];
		if (not p)return;
		ll val = lens[p];
		bit_has.add(mul, p);
		bit_pos.add(mul*p, p);
		bit_psum.add(mul*val, p);
		bit_prod.add(mul*val*p, p);
	};
	auto query_r = [&](int p, int cs){
		int l = max(1, p-cs), r = p;
		ll q_l = bit_has.query(l, r);
		ll sum_l = bit_pos.query(l, r);
		ll sum_pl = bit_psum.query(l, r);
		ll sum_l_pl = bit_prod.query(l, r);
		ll pr = lens[r];
		return 4 * (r * pr * q_l  - r * sum_pl - sum_l * pr + sum_l_pl);
		
	};
	auto query_l = [&](int p, int cs){
		int l = p, r = min(n, p+cs);
		ll q_r = bit_has.query(l, r);
		ll sum_r = bit_pos.query(l, r);
		ll sum_pr = bit_psum.query(l, r);
		ll sum_r_pr = bit_prod.query(l, r);
		ll pl = lens[l];
		return 4 * (sum_r_pr - sum_r * pl - l * sum_pr + l * pl * q_r);
	};
	auto query = [&](int i, int cs){
		int p = epos[i];
		if (not p)return 0ll;
		return query_r(p, cs) + query_l(p, cs);
	};
	
	ll ans = 0;
	auto dfsstl = [&](auto rec, int v, int keep)->void {
		int b = big[v];
		for(int f : g[v])if (f != b)rec(rec, f, 0);
		if (b != -1)rec(rec, b, 1);
		int cs = clen[v];
		ans += query(v, cs);
		update(v, 1);
		for(int f : g[v])if (f != b){
			for(int i = pos[f]; i < pos[f]+sub[f]; i++)ans += query(pre[i], cs);
			for(int i = pos[f]; i < pos[f]+sub[f]; i++)update(pre[i], 1);
		}
		if (not keep)for(int i = pos[v]; i < pos[v]+sub[v]; i++)update(pre[i], -1);
	};
	dfsstl(dfsstl, 1, 0);
	
	cout << ans << endl;
}

The sum of the total time spent to select a parking spot and the distance of the finally selected spot will be called the \textbf{penalty}.

For each $$$i \in [1, n]$$$, let $$$f(i)$$$ be the expected value of the penalty, given that Henrique started the process from spot $$$i$$$ (acting optimally). What we want to compute is $$$f(1)$$$. If $$$S(i)$$$ is the next spot after $$$i$$$ (that is, $$$S(i)=i+1$$$ if $$$i \neq n$$$ and $$$S(n) = 1$$$), we have

.

Defining

we have $$$f(i) = s_i(f(S(i)))$$$, hence $$$f(1) = (s_1 \circ s_2 \circ \dots \circ s_n) (f(1))$$$. Denoting the composition $$$s_1 \circ \dots \circ s_n$$$ by $$$s$$$, we have $$$f(1)=s(f(1))$$$.

We will analyze the behavior of the function $$$s = s_1 \circ s_2 \circ \dots \circ s_n$$$ to show that it has exactly one fixed point. Since we have already seen that $$$f(1)$$$ is a fixed point of $$$s$$$ (that is, $$$f(1) = s(f(1))$$$), it will be enough to find this fixed point, which can be done with a binary search to find a zero of $$$s(x)-x$$$, since this function is clearly continuous.

Note that, for $$$x \le d_i-1$$$, we have $$$s_i(x)=1+x$$$. On the other hand, for $$$x \ge d_i-1$$$, we have $$$s_i(x) = p_i d_i + (1-p_i)(1+x)$$$, which is a line with slope $$$1-p_i \in (0,1)$$$. Thus, we see that, for sufficiently small values of $$$x$$$, $$$s(x) = x + n$$$. After that, $$$s(x)$$$ is piecewise linear, formed by several lines with slopes in the interval $$$(0,1)$$$. Therefore, the function $$$s(x)-x$$$ is initially constant and equal to $$$n$$$, and then is given by several lines with slopes in the interval $$$(-1,0)$$$. In other words, $$$s(x)-x$$$ is initially constant and positive, and then is strictly decreasing, eventually becoming a line with negative slope. Since it is continuous, this proves that it has exactly one root, so $$$s$$$ has exactly one fixed point, as desired.

Since we can compute $$$s(x)-x$$$ naively in $$$\mathcal{O}(n)$$$, using binary search we can find its unique $$$0$$$ with precision $$$\epsilon$$$ in $$$\mathcal{O}(n \log(1 / \epsilon))$$$.

#include <bits/stdc++.h>
 
using namespace std;
 
constexpr int ITER = 70;
 
signed main() {
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n;cin>>n;
	vector<int> ds(n);	
	vector<double> ps(n);
	for (auto& d : ds) cin >> d;
	for (auto& p : ps) cin >> p;
 
	auto check=[&](double val) {
		for (int i=n-1; i>=0; i--)
			val=ps[i] * (min(1+val, (double)ds[i])) + (1-ps[i]) * (1+val);
		return val;
	};
 
	double l=0, r = 1e8;
	for (int i = 0; i < ITER; i++) {
		double mid = (l+r)/2;
		if (check(mid) < mid) r=mid;
		else l=mid;
	}
 
	cout << fixed << setprecision(20);
	cout << (l+r)/2 << endl;
}

The problem asks, for every $$$i$$$ from $$$1$$$ to $$$M$$$, for the sum of the values (ratings) greater than or equal to $$$i$$$.

Note that the sum of the values greater than or equal to $$$i$$$ is equal to the sum of the values greater than or equal to $$$i+1$$$ plus the sum of the values equal to $$$i$$$. To solve the problem, we will use the auxiliary arrays $$$f$$$ and $$$ans$$$. We will store in $$$f_i$$$ the number of problems with rating $$$i$$$, and we will use this to store the answer requested by the statement for $$$i$$$ in $$$ans_i$$$.

We will iterate over every $$$i$$$ from $$$M$$$ down to $$$1$$$ (decreasing $$$i$$$): the answer for $$$i$$$ is simply the answer for $$$i+1$$$ (already computed previously and stored in $$$ans_{i+1}$$$) plus $$$i \cdot f_i$$$ (the sum of the ratings of the problems equal to $$$i$$$ — simply the product of the rating by the number of corresponding problems). Then, it is enough to iterate over $$$i$$$ in increasing order and print the answer in $$$ans_i$$$.

The complexity of this solution is $$$O(N+M)$$$.

#include<bits/stdc++.h>
using namespace std;
 
int main(){
	cin.tie(0)->sync_with_stdio(0);
	int n, m; 
	cin >> n >> m;
	vector ratings(m+1, 0);
	for(int i = 0; i < n; i++){
		int r;
		cin >> r;
		ratings[r]++;
	}
	vector ans(m+2, 0ll);
	for(int r = m; r > 0; r--)ans[r] = ans[r+1] + (long long) ratings[r] * r;
	for(int i = 1; i <= m; i++)cout << ans[i] << ' ';
	cout << '\n';
}