• Excellent contest
• Good contest
• Average contest
• Bad contest
• Horrible contest

• Trivial contest
• Easy contest
• Average contest
• Hard contest
• Impossible contest

If $$$n$$$ is odd, there are clearly zero possible configurations.

Suppose $$$n$$$ is even. Then consider the number of legs that belong to cows. This can be any multiple of $$$4$$$ that is less than or equal to $$$n$$$. The remaining legs will belong to chickens. Thus, the answer is equal to the number of nonnegative multiples of $$$4$$$ which are less than or equal to $$$n$$$, which is given by $$$\lfloor \frac{n}{4} \rfloor + 1$$$.

#include <bits/stdc++.h>
using namespace std;
 
void solve(){
    int n;
    cin >> n;
    cout << (n & 1 ? 0 : n/4+1) << '\n';
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while(t--) solve();
}

• Excellent problem
• Good problem
• Average problem
• Bad problem
• Horrible problem

• Trivial problem
• Easy problem
• Average problem
• Hard problem
• Impossible problem

The given expression is equal to $$$|(a_2 - a_1) + (a_3 - a_2) + \dots + (a_n - a_{n-1})|$$$.

This simplifies to $$$|a_n - a_1|$$$.

We want to minimize the absolute difference between the first and last elements. To do so, if one of them is set and the other one isn't, we will set them to be equal. Now, the remaining blank elements do not affect the given expression, so we can set them all to be zero.

#include <bits/stdc++.h>
using namespace std;
 
void solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i=0; i<n; i++)
        cin >> a[i];
    if(a[0] == -1)
        a[0] = a[n-1];
    if(a[n-1] == -1)
        a[n-1] = a[0];
    for(int i=0; i<n; i++)
        if(a[i] == -1)
            a[i] = 0;
    cout << abs(a[n-1] - a[0]) << '\n';
    for(int i=0; i<n; i++)
        cout << a[i] << " \n"[i == n-1];
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while(t--) solve();
}

• Excellent problem
• Good problem
• Average problem
• Bad problem
• Horrible problem

• Trivial problem
• Easy problem
• Average problem
• Hard problem
• Impossible problem

The $$$\mathrm{XOR}$$$ of all $$$2n$$$ elements is invariant. Note that this is also equal to the $$$\mathrm{XOR}$$$ between Ajisai and Mai's final scores. Therefore, if this value is zero, the game ends in a tie. Otherwise, Ajisai and Mai's final scores will differ, so the game does not end in a tie.

Suppose the $$$\mathrm{XOR}$$$ of all $$$2n$$$ elements is nonzero. If $$$a_i = b_i$$$, then the $$$i$$$-th turn is useless. Now, consider the largest $$$i$$$ such that $$$a_i \neq b_i$$$. This person can control whose score is $$$0$$$ and whose score is $$$1$$$. Since all future turns are useless, they win. Therefore, if the largest $$$i$$$ satisfying $$$a_i \neq b_i$$$ is odd, Ajisai wins. Otherwise, Mai wins.

#include <bits/stdc++.h>
using namespace std;
 
void solve(){
    int n, x = 0, idx;
    cin >> n;
    vector<int> a(n), b(n);
    for(int i=0; i<n; i++){
        cin >> a[i];
        x ^= a[i];
    }
    for(int i=0; i<n; i++){
        cin >> b[i];
        x ^= b[i];
    }
    if(!x){
        cout << "Tie" << '\n';
        return;
    }
    for(int i=0; i<n; i++)
        if(a[i] ^ b[i])
            idx = i;
    cout << (idx & 1 ? "Mai" : "Ajisai") << '\n';
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while(t--) solve();
}

The $$$\mathrm{XOR}$$$ of all $$$2n$$$ elements is equal to the $$$\mathrm{XOR}$$$ between Ajisai and Mai's final scores. Therefore, we know exactly what bits their scores will differ in.

The most significant of these bits dictates who wins the game. Therefore, we can apply the solution from the easy version to the most significant bit of the $$$\mathrm{XOR}$$$ of all $$$2n$$$ elements.

#include <bits/stdc++.h>
using namespace std;
 
void solve(){
    int n, x = 0, bit, idx;
    cin >> n;
    vector<int> a(n), b(n);
    for(int i=0; i<n; i++){
        cin >> a[i];
        x ^= a[i];
    }
    for(int i=0; i<n; i++){
        cin >> b[i];
        x ^= b[i];
    }
    if(!x){
        cout << "Tie" << '\n';
        return;
    }
    for(int i=0; i<20; i++)
        if(x&1<<i)
            bit = i;
    for(int i=0; i<n; i++)
        if((a[i]^b[i])&1<<bit)
            idx = i;
    cout << (idx & 1 ? "Mai" : "Ajisai") << '\n';
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while(t--) solve();
}

• Excellent problem
• Good problem
• Average problem
• Bad problem
• Horrible problem

• Trivial problem
• Easy problem
• Average problem
• Hard problem
• Impossible problem

Let $$$\mathrm{pre}_i$$$ denote the minimum of $$$p_1, \dots, p_i$$$, and let $$$\mathrm{suf}_i$$$ denote the maximum of $$$p_i, \dots, p_n$$$. Then if there exists some $$$i$$$ such that $$$\mathrm{pre}_{i-1} \gt \mathrm{suf}_i$$$, then the answer is $$$\texttt{No}$$$. This is because there is no edge from any value in $$$p_1, \dots, p_{i-1}$$$ to any value in $$$p_i, \dots, p_n$$$.

Otherwise, suppose that for every $$$i$$$, we have that $$$\mathrm{pre}_{i-1} \lt \mathrm{suf}_i$$$. Then for every $$$i$$$, we have that there exists a path from $$$p_{i-1}$$$ to $$$p_i$$$, by going from $$$p_{i-1}$$$ to $$$\mathrm{pre}_{i-1}$$$ to $$$\mathrm{suf}_i$$$ to $$$p_i$$$. Since the graph consisting of these paths is connected, it must have some spanning tree, so the answer is $$$\texttt{Yes}$$$.

#include <bits/stdc++.h>
using namespace std;
 
void solve(){
    int n;
    cin >> n;
    vector<int> p(n+1), pre(n+1, n), suf(n+2);
    for(int i=1; i<=n; i++){
        cin >> p[i];
        pre[i] = min(pre[i-1], p[i]);
    }
    for(int i=n; i>=1; i--)
        suf[i] = max(suf[i+1], p[i]);
    for(int i=2; i<=n; i++)
        if(pre[i-1] > suf[i]){
            cout << "No" << '\n';
            return;
        }
    cout << "Yes" << '\n';
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while(t--) solve();
}

Suppose that $$$\mathrm{pre}_{i-1} \lt \mathrm{suf}_i$$$ for all $$$i$$$. Let $$$s_1 \lt \dots \lt s_k = n$$$ denote the indices satisfying $$$p_i = \mathrm{suf}_i$$$, that is, the suffix maxes of $$$p$$$. Then let's partition $$$p$$$ into blocks ending at each $$$s_i$$$. Now, consider a block consisting of $$$p[l, r]$$$ for $$$l=s_{i-1}+1$$$ and $$$r=s_i$$$. We have that $$$\mathrm{suf}_l = \mathrm{suf}_r = p_r$$$ by construction, which means that all values in $$$p[l, r-1]$$$ are less than $$$p_r$$$. So we can connect all of these values to $$$p_r$$$.

Now, each block is connected, so it suffices to connect the blocks to each other. We have that $$$\mathrm{pre}_{l-1} \lt \mathrm{suf}_l = p_r$$$, so we can connect $$$p_r$$$ to $$$\mathrm{pre}_{l-1}$$$. By induction, we see that all blocks are now connected, since each block is connected to some previous block.

#include <bits/stdc++.h>
using namespace std;
 
void solve(){
    int n;
    cin >> n;
    vector<int> p(n+1), pre(n+1, n);
    vector<pair<int, int>> suf(n+2);
    for(int i=1; i<=n; i++){
        cin >> p[i];
        pre[i] = min(pre[i-1], p[i]);
    }
    for(int i=n; i>=1; i--)
        suf[i] = max(suf[i+1], {p[i], i});
    for(int i=2; i<=n; i++)
        if(pre[i-1] > suf[i].first){
            cout << "No" << '\n';
            return;
        }
    cout << "Yes" << '\n';
    for(int l=1; l<=n;){
        int r = suf[l].second;
        for(int i=l; i<r; i++)
            cout << p[i] << ' ' << p[r] << '\n';
        if(l > 1)
            cout << pre[l-1] << ' ' << p[r] << '\n';
        l = r+1;
    }
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while(t--) solve();
}

• Excellent problem
• Good problem
• Average problem
• Bad problem
• Horrible problem

• Trivial problem
• Easy problem
• Average problem
• Hard problem
• Impossible problem

Let $$$x$$$'s denote elements which all share a common divisor, and let $$$-$$$'s denote any elements. Then an array of the form $$$[-, x, x, -, x, x, \dots]$$$ will have no bad indices. Let's call an array of this form "perfect".

Suppose the $$$x$$$'s are even elements. We have roughly $$$\frac{n}{2}$$$ even elements, which means we can form a perfect array of length roughly $$$\frac{3n}{4}$$$. Now, we have roughly $$$\frac{n}{6}$$$ elements which are odd multiples of $$$3$$$, which means we can form a disjoint perfect array of length roughly $$$\frac{n}{4}$$$. By concatenating these two arrays, we achieve a roughly full permutation with $$$O(1)$$$ bad indices. See the next section for a proof of the bound on bad indices.

Instead of counting bad indices, we will count good indices. We form a perfect array of length $$$3\lfloor \frac{n}{4} \rfloor$$$, where all indices are good except for potentially the last one. We also form a perfect array of length $$$3\lfloor \frac{n+3}{12} \rfloor$$$ because we gain a new triple for every pair of $$$\{3, 9\} \pmod{12}$$$. Again, all indices are good except for potentially the last one. Therefore, we achieve $$$3\lfloor \frac{n}{4}\rfloor + 3\lfloor \frac{n+3}{12} \rfloor - 2$$$ good indices. It can be verified for every residue class $$$\bmod 12$$$ that this is lower bounded by $$$n-6$$$. Since there are $$$n-2$$$ indices in total, we have at most $$$4$$$ bad indices.

#include <bits/stdc++.h>
using namespace std;
 
void solve(){
    int n;
    cin >> n;
    vector<vector<int>> a(3);
    for(int i=1; i<=n; i++)
        if(!(i % 2))
            a[0].push_back(i);
        else if(!(i % 3))
            a[1].push_back(i);
        else
            a[2].push_back(i);
    while(a[2].size() >= 1 && a[0].size() >= 2){
        cout << a[2].back() << ' ';
        a[2].pop_back();
        cout << a[0].back() << ' ';
        a[0].pop_back();
        cout << a[0].back() << ' ';
        a[0].pop_back();
    }
    while(a[2].size() >= 1 && a[1].size() >= 2){
        cout << a[2].back() << ' ';
        a[2].pop_back();
        cout << a[1].back() << ' ';
        a[1].pop_back();
        cout << a[1].back() << ' ';
        a[1].pop_back();
    }
    for(int i : a[0])
        cout << i << ' ';
    for(int i : a[1])
        cout << i << ' ';
    for(int i : a[2])
        cout << i << ' ';
    cout << '\n';
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while(t--) solve();
}

A construction commented by d1amondzz seems to prove an upper bound of $$$f(3), f(5) \leq 1$$$ and $$$f(n) = 0$$$ for $$$n\neq 3, 5$$$. I think several other comments may have alluded to a similar solution as well. The general idea is that for the largest prefix of primes $$$p_1, ..., p_k$$$ satisfying $$$p_{k-1}\cdot p_k \leq n$$$, we can construct an array $$$q$$$ as follows: for each $$$p_i$$$, first append $$$p_i$$$ to $$$q$$$, then append all elements with smallest prime factor $$$p_i$$$, ending with $$$p_i\cdot p_{i+1}$$$. Then all adjacent elements are not coprime, so as long as this array is of size at least roughly $$$\frac{2}{3}n$$$, we can intersperse it with the remaining elements to achieve no bad indices. All composites are included in $$$q$$$, because if a composite number has smallest prime factor at least $$$p_{k+1}$$$, then its value is at least $$$(p_{k+1})^2 \gt p_k\cdot p_{k+1} \gt n$$$ by construction of $$$k$$$. So we have that $$$q$$$ is of length asympototically at least $$$n-\frac{n}{\log n}$$$, which is asymptotically at least $$$cn$$$ for any $$$c \lt 1$$$. We can furthermore verify that this construction works for all small $$$n$$$ except for $$$3$$$ and $$$5$$$.

As for the lower bound, it's easy to see that $$$f(3) \geq 1$$$ since all pairs are coprime, and that $$$f(5) \geq 1$$$ since the only pair that is not coprime is $$$\{2, 4\}$$$, but we cannot have that these elements appear in all triples. Therefore, we have that $$$f(3) = f(5) = 1$$$ and $$$f(n) = 0$$$ for $$$n\neq 3, 5$$$.

• Excellent problem
• Good problem
• Average problem
• Bad problem
• Horrible problem

• Trivial problem
• Easy problem
• Average problem
• Hard problem
• Impossible problem

Let's fix the number of double operations we use; call this integer $$$k$$$. Now, we can treat each value independently.

Consider a specific pair $$$a_i, b_i$$$. If we don't apply any addition operations, we have that $$$a_i$$$ becomes $$$a_i \cdot 2^k$$$. Clearly we need that $$$a_i \cdot 2^k \leq b_i$$$. Now, observe that applying an addition operation before applying $$$j$$$ of the $$$k$$$ double operations is equivalent to adding $$$2^j$$$ to our final sum. We need to add $$$b_i - a_i \cdot 2^k$$$, so in total, we apply $$$\lfloor \frac{b_i - a_i \cdot 2^k}{2^k} \rfloor = \lfloor \frac{b_i}{2^k} \rfloor - a_i$$$ addition operations at the beginning, each adding $$$2^k$$$ to our sum. Then, we apply $$$\texttt{popcount}((b_i - a_i \cdot 2^k)\pmod{2^k}) = \texttt{popcount}(b_i\pmod{2^k})$$$ addition operations later, where $$$\texttt{popcount}(x)$$$ denotes the number of set bits in $$$x$$$. This is because, if the $$$j$$$-th bit of $$$b_i - a_i \cdot 2^k$$$ is set for some $$$j \lt k$$$, we would like to apply an operation before applying $$$j$$$ of the double operations so we can add $$$2^j$$$ to our sum.

We would like to choose the largest number of double operations possible, since a double operation increases all values by at least one. Furthermore, since $$$n\geq 2$$$, a double operation is strictly more effective than an addition operation. However, we still need to satisfy $$$a_i \cdot 2^k \leq b_i$$$ for all $$$i$$$. Therefore, we will choose $$$k=\min \log_2{\frac{b_i}{a_i}}$$$.

Between each double operation, the addition operations can be rearranged. Let's consider all of the addition operations applied before applying exactly $$$j$$$ double operations; denote these values $$$c_1, \dots, c_n$$$, where $$$c_i$$$ is the number of addition operations performed on element $$$a_i$$$. Then we can multiply our number of sequences by $$${\sum c_i \choose c_1, \dots, c_n}$$$, the multinomial coefficient of $$$c_i$$$. This is equal to $$$\frac{(\sum c_i)!}{\prod (c_i!)}$$$. To simplify implementation, note that for $$$j \lt k$$$, all $$$c_i$$$ are either $$$0$$$ or $$$1$$$, so the denominator is only nontrivial for $$$j=k$$$. The final answer is the product of these values across all $$$0\leq j\leq k$$$. See the next section for intuition on multinomial coefficients and some of the details on its implementation.

The intuition behind the formula for multinomial coefficients is as follows: let's say $$$n=3$$$, and we want to find the number of ways to color $$$\sum c_i$$$ balls such that $$$c_1$$$ are red, $$$c_2$$$ are green, and $$$c_3$$$ are blue. Let's call our positions "red $$$1$$$" $$$\dots$$$ "red $$$c_1$$$" $$$\dots$$$ "blue $$$c_3$$$". Now, it's clear that there are $$$(\sum c_i)!$$$ ways to assign each ball to a position, because we have $$$\sum c_i$$$ choices of balls to assign to "red $$$1$$$", then $$$\sum c_i - 1$$$ remaining choices of balls to assign to "red $$$2$$$", and so forth, until we only have one choice of balls to assign to "blue $$$c_3$$$". However, this overcounts, because there is no difference between assigning ball $$$1$$$ to "red $$$1$$$" and ball $$$2$$$ to "red $$$2$$$", and vice versa. We are overcounting the red assignments by a factor of $$$c_1!$$$, because every valid selection of red balls achieves $$$c_1!$$$ assignments of red balls to positions. Similar reasoning holds for the green and blue balls, so in total, we have $$$\frac{(\sum c_i)!}{\prod (c_i!)}$$$ different sequences.

Multinomial coefficients can be computed by precomputing factorials. For the numerator, note that if $$$\sum c_i \geq 10^6+3$$$ then $$$(\sum c_i)! \equiv 0\pmod{10^6+3}$$$ because we have a factor of $$$10^6+3$$$, so we only need to precompute factorials up to $$$10^6+2$$$. For the denominator, we can divide by $$$c_i!$$$ by multiplying by the modular inverse of $$$c_i!$$$ modulo $$$10^6+3$$$. Crucially, note that $$$c_i \lt 10^6+3$$$ because the number of addition operations you can apply is at most $$$b_i - a_i \lt 10^6$$$, so modular inverses are well-defined.

#include <bits/stdc++.h>
#define int long long
using namespace std;
 
int mod = 1e6+3;
 
vector<int> fact(mod);
 
int inv(int a){
    return a <= 1 ? a : mod - mod / a * inv(mod % a) % mod;
}
 
void solve(){
    int n, x, ans = 1;
    cin >> n;
    vector<int> a(n), b(n);
    for(int i=0; i<n; i++)
        cin >> a[i];
    for(int i=0; i<n; i++)
        cin >> b[i];
    int k = __lg(b[0] / a[0]);
    for(int i=1; i<n; i++)
        k = min(k, __lg(b[i] / a[i]));
    x = k;
    vector<int> cnt(k), c(n);
    for(int i=0; i<n; i++){
        for(int j=0; j<k; j++){
            cnt[j] += b[i] & 1;
            b[i] >>= 1;
        }
        c[i] = b[i] - a[i];
    }
    for(int j=0; j<k; j++){
        x += cnt[j];
        ans = ans * fact[cnt[j]] % mod;
    }
    int last = accumulate(c.begin(), c.end(), 0LL);
    ans = (last < mod ? ans * fact[last] % mod : 0);
    for(int i : c){
        x += i;
        ans = ans * inv(fact[i]) % mod;
    }
    cout << x << ' ' << ans << '\n';
}
 
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    fact[0] = 1;
    for(int i=1; i<mod; i++) fact[i] = fact[i-1] * i % mod;
    int t;
    cin >> t;
    while(t--) solve();
}

• Excellent problem
• Good problem
• Average problem
• Bad problem
• Horrible problem

• Trivial problem
• Easy problem
• Average problem
• Hard problem
• Impossible problem

Let's first try to solve this problem with inefficient time and memory, then we will later optimize it. For $$$1\leq i\leq n$$$ and $$$0\leq j\leq m-n$$$, let $$$\mathrm{dp}[i][j]$$$ denote the largest score achievable from the first $$$i$$$ indices, while also satisfying $$$a_i = i+j$$$. Now, since $$$a$$$ must be strictly increasing, we equivalently have that $$$a_i - i$$$ is monotonically increasing. Therefore, we can transition as follows: $$$\mathrm{dp}[i][j] = \max_{k\leq j} \mathrm{dp}[i-1][k] + v(i, i+j)$$$, because we may choose $$$a_{i-1}$$$ to be any value satisfying $$$a_{i-1} - (i-1) \leq j$$$, then we choose $$$a_i = i+j$$$, adding a score of $$$v(i, i+j)$$$.

Now, we will try to remove the first dimension; that is, $$$\mathrm{dp}[j]$$$ denotes the largest score achievable while also satisfying $$$a_i = i+j$$$, where we will update this array as we iterate through all $$$i$$$. We will store this in a data structure that supports quickly querying prefix maximums and increasing point values; in particular, either a Fenwick tree or a segment tree will work.

Suppose we are at some stage $$$i$$$ and would like to update $$$\mathrm{dp}[j]$$$. As before, we want to update it to $$$\max_{k\leq j} \mathrm{dp}[k] + v(i, i+j)$$$. We should process $$$j$$$ in reverse order, as we want to ensure that we are accessing $$$\mathrm{dp}[i-1][k]$$$ instead of $$$\mathrm{dp}[i][k]$$$.

However, we only have to update $$$\mathrm{dp}[j]$$$ if $$$v(i, i+j)$$$ is nonzero. This is because, if $$$v(i, i+j)$$$ is zero, then we are updating $$$\mathrm{dp}[j]$$$ to $$$\max_{k\leq j} \mathrm{dp}[k]$$$. However, since we are only querying prefix maximums, any query involving $$$j$$$ will implicitly query all $$$k\leq j$$$ anyways, so it is not necessary to explicitly update $$$\mathrm{dp}[j]$$$. Our final answer is $$$\max \mathrm{dp}[j]$$$. See the next section for runtime analysis.

For simplicity of analysis, assume $$$m - n \geq c$$$ for some reasonable $$$c$$$, to avoid pathological cases where $$$\log (m-n)$$$ is undefined or zero.

For each $$$i$$$, we are updating $$$O(\frac{m-n}{i})$$$ values. Therefore, in total, we have $$$O(\sum \frac{m-n}{i}) = O((m-n)H(n))$$$ updates. Since harmonic numbers are known to grow logarithmically, this is $$$O((m-n)\log n)$$$. Each update takes $$$O(\log (m-n))$$$ time, as it involves a query and an update on a Fenwick tree or segment tree of size $$$m-n+1$$$. So the updates in total take $$$O((m-n)\log n\log{(m-n)})$$$ time.

However, we also need to compute $$$v(i, i+j)$$$ for each update. This will take $$$O(\sum v(i, i+j))$$$ time. For a fixed $$$i$$$, we have that $$$O(\frac{m-n}{i})$$$ values satisfy $$$v(i, i+j) \geq 1$$$, $$$O(\frac{m-n}{i^2})$$$ values satisfy $$$v(i, i+j) \geq 2$$$, and so forth. Therefore, for a fixed $$$i$$$, we have that $$$\sum v(i, i+j) = O(\sum \frac{m-n}{i^k}) = O(\frac{m-n}{i}\sum \frac{1}{i^{k-1}}) = O(\frac{m-n}{i} \cdot \frac{1}{1-\frac{1}{i}}) = O(\frac{m-n}{i} \cdot \frac{i}{i-1}) = O((m-n) \cdot \frac{1}{i-1})$$$. Across all $$$i\geq 2$$$, we have $$$O((m-n)H(n-1)) = O((m-n)\log n)$$$. This is dominated by the $$$O((m-n)\log n\log{(m-n)})$$$ term from the updates.

Finally, we have an additional $$$n$$$ term, as we have to iterate through all $$$i\leq n$$$. Our total runtime is $$$O((m-n)\log n\log{(m-n)} + n)$$$.

#include <bits/stdc++.h>
using namespace std;
 
void solve(){
    int n, m;
    cin >> n >> m;
    vector<int> mx(m-n+1);
    function<int(int)> query = [&](int i)->int{
        int ret = 0;
        for(; i>=0; i=(i&i+1)-1)
            ret = max(ret, mx[i]);
        return ret;
    };
    function<void(int, int)> update = [&](int i, int val){
        for(; i<=m-n; i|=i+1)
            mx[i] = max(mx[i], val);
    };
    function<int(int, int)> v = [](int b, int x)->int{
        int ans = 0;
        while(!(x % b)){
            ans++;
            x /= b;
        }
        return ans;
    };
    for(int i=2; i<=n; i++)
        for(int j=(m-n+i)/i*i; j>=i; j-=i)
            update(j-i, query(j-i) + v(i, j));
    cout << query(m-n) << '\n';
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while(t--) solve();
}

• Excellent problem
• Good problem
• Average problem
• Bad problem
• Horrible problem

• Trivial problem
• Easy problem
• Average problem
• Hard problem
• Impossible problem

• Excellent contest
• Good contest
• Average contest
• Bad contest
• Horrible contest

• Trivial contest
• Easy contest
• Average contest
• Hard contest
• Impossible contest

Alice can't lose unless there are no numbers remaining on her turn (in particular, this can only occur if $$$n$$$ is even). So Bob's job is to pair all numbers into disjoint pairs $$$(a, b)$$$ with $$$a+b\equiv 3\pmod 4$$$. If he can do so, he wins by choosing the paired number to each of Alice's choices. Otherwise, Alice wins.

It doesn't really matter if Bob chooses, say, $$$0$$$ or $$$4$$$, because it won't affect the value of $$$a+b\pmod 4$$$. That is, two values are essentially identical in this game if they are equivalent $$$\bmod 4$$$. So now, the numbers on the blackboard are essentially $$$0, 1, 2, 3, 0, 1, 2, 3, \dots (n-1)\pmod 4$$$.

Now, all of the numbers on the blackboard are either $$$0$$$, $$$1$$$, $$$2$$$, or $$$3$$$. It is clear that Bob must pair $$$0$$$ with $$$3$$$, and $$$1$$$ with $$$2$$$. So Bob wins if the number of $$$0$$$'s is the same as the number of $$$3$$$'s, and the number of $$$1$$$'s is the same as the number of $$$2$$$'s.

#include <bits/stdc++.h>
using namespace std;
 
void solve(){
    int n;
    cin >> n;
    vector<int> cnt(4);
    for(int i=0; i<n; i++)
        cnt[i % 4]++;
    cout << (cnt[0] == cnt[3] && cnt[1] == cnt[2] ? "Bob" : "Alice") << '\n';
}
 
int main(){
    int t;
    cin >> t;
    while(t--) solve();
}

For an $$$O(1)$$$ solution, observe that as $$$n$$$ increases, a $$$0$$$, $$$1$$$, $$$2$$$, and $$$3$$$ are introduced, in that order. So the number of $$$0$$$'s can only match the number of $$$3$$$'s, and the number of $$$1$$$'s can only match the number of $$$2$$$'s, if $$$n$$$ is a multiple of $$$4$$$.

#include <bits/stdc++.h>
using namespace std;
 
void solve(){
    int n;
    cin >> n;
    cout << (n % 4 ? "Alice" : "Bob") << '\n';
}
 
int main(){
    int t;
    cin >> t;
    while(t--) solve();
}

• Excellent problem
• Good problem
• Average problem
• Bad problem
• Horrible problem

• Trivial problem
• Easy problem
• Average problem
• Hard problem
• Impossible problem

If $$$k \gt 1$$$, then the answer is always $$$\texttt{YES}$$$. This is because player $$$j$$$ might never get picked.

If $$$k=1$$$, then we claim that the answer is only $$$\texttt{YES}$$$ if player $$$j$$$ has the maximum strength across all players. Indeed, consider the set of players with maximum strength. It is impossible for all of them to get eliminated, because the last one of them can't possibly lose a match. So at least one of these players will be remaining at the end of the game. If player $$$j$$$ is not one of these players, they cannot be the last player remaining.

#include <bits/stdc++.h>
using namespace std;
 
void solve(){
    int n, j, k, mx = 0;
    cin >> n >> j >> k;
    vector<int> a(n+1);
    for(int i=1; i<=n; i++){
        cin >> a[i];
        mx = max(mx, a[i]);
    }
    cout << (k > 1 || a[j] == mx ? "YES" : "NO") << '\n';
}
 
int main(){
    int t;
    cin >> t;
    while(t--) solve();
}

• Excellent problem
• Good problem
• Average problem
• Bad problem
• Horrible problem

• Trivial problem
• Easy problem
• Average problem
• Hard problem
• Impossible problem

If $$$a$$$ has size $$$2$$$, we can make either of its elements the last one. We can transform $$$a$$$ into $$$\min(a_1, a_2)$$$ by choosing the prefix of size $$$2$$$, and we can transform $$$a$$$ into $$$\max(a_1, a_2)$$$ by choosing the suffix of size $$$2$$$.

If $$$a_i$$$ is a prefix min, now we can transform $$$a$$$ into $$$[a_i]$$$. We do so by first choosing the prefix of length $$$i$$$. Now, $$$a_i$$$ is the first element of $$$a$$$. If $$$a$$$ is of size $$$1$$$, we are done. Otherwise, we can choose the suffix consisting of all of the elements after it. Now, our array is of size $$$2$$$, so we can transform $$$a$$$ into $$$[a_i]$$$ as desired. By identical reasoning, if $$$a_i$$$ is a suffix max, we can transform $$$a$$$ into $$$[a_i]$$$.

Now, suppose that $$$a_i$$$ is not a prefix min or a suffix max. Then let $$$a_p$$$ be the min of the prefix $$$[a_1, \dots, a_i]$$$, and let $$$a_s$$$ be the max of the suffix $$$[a_i, \dots, a_n]$$$. Note that $$$p \lt i \lt s$$$ and $$$a_p \lt a_i \lt a_s$$$.

We claim that it is impossible to remove $$$a_p$$$ or $$$a_s$$$ without removing $$$a_i$$$. Consider the first operation which removes (at least) one of $$$a_p$$$, $$$a_i$$$, or $$$a_s$$$.

• Suppose you remove $$$a_p$$$ by choosing a prefix which includes an element smaller than $$$a_p$$$. Since $$$a_p$$$ is the smallest element in $$$[a_1, \dots, a_i]$$$, this means that you must have chosen at least one element after $$$a_i$$$. But then this prefix also includes $$$a_i$$$. Since $$$a_i$$$ is not the min of this prefix, it will also be removed. By identical reasoning, if you remove $$$a_s$$$ by choosing a suffix which includes an element larger than $$$a_s$$$, then $$$a_i$$$ will also be removed.
• Conversely, suppose you remove $$$a_p$$$ by choosing a suffix which includes $$$a_p$$$. But then this suffix will include $$$a_i$$$ and $$$a_s$$$. Since $$$a_i$$$ is not the max of this suffix, it will also be removed. By identical reasoning, if you remove $$$a_s$$$ by choosing a prefix which includes $$$a_s$$$, then $$$a_i$$$ will also be removed.

So the first operation that removes one of $$$a_p$$$, $$$a_i$$$, or $$$a_s$$$ will necessarily remove $$$a_i$$$, so it is impossible to transform $$$a$$$ into $$$[a_i]$$$.

#include <bits/stdc++.h>
using namespace std;
 
void solve(){
    int n;
    cin >> n;
    vector<int> a(n+1), pre(n+1, INT_MAX), suf(n+2);
    for(int i=1; i<=n; i++){
        cin >> a[i];
        pre[i] = min(pre[i-1], a[i]);
    }
    for(int i=n; i>=1; i--)
        suf[i] = max(suf[i+1], a[i]);
    for(int i=1; i<=n; i++)
        cout << (a[i] == pre[i] || a[i] == suf[i] ? 1 : 0);
    cout << '\n';
}
 
int main(){
    int t;
    cin >> t;
    while(t--) solve();
}

• Excellent problem
• Good problem
• Average problem
• Bad problem
• Horrible problem

• Trivial problem
• Easy problem
• Average problem
• Hard problem
• Impossible problem

Let $$$\mathrm{cnt}$$$ be the number of ones in $$$s$$$. Then clearly if $$$\mathrm{cnt} \leq k$$$, Alice can win immediately.

Now, let's reframe Bob's win condition. Bob can win if and only if he can ensure that, before each of Alice's turns, there are at least $$$k+1$$$ ones in $$$s$$$. In other words, he has to ensure that after each of his turns, $$$\mathrm{cnt} \gt k$$$. Clearly, after each of Bob's turns, $$$\mathrm{cnt} \geq k$$$, since the entire substring he chose is all ones. So he only has to ensure that there is at least one other extra one in $$$s$$$.

If $$$\mathrm{cnt} \gt k$$$ and $$$n\geq 2\cdot k$$$, then Bob can always win. Indeed, on each of Bob's turns, he can pick any existing one in $$$s$$$ to be the extra one. Now, he simply has to choose a substring which doesn't contain this extra one. Then there will be at least $$$k+1$$$ ones; the $$$k$$$ from the substring he chose, and the extra one. If $$$n\geq 2\cdot k$$$, then there must be at least $$$k$$$ elements to either the left or the right of this one, so Bob can choose such a substring.

For example, consider $$$n=8$$$ and $$$k=4$$$. Suppose, before Bob's turn, $$$s=00100010$$$. Then Bob chooses any arbitrary existing one in $$$s$$$, say, the one in the third position. Now, he would like to choose a substring of length $$$k$$$ which does not include the third position. In this case, he can choose the substring $$$s[5, 8]$$$. Now, after his turn, $$$s=00101111$$$. As desired, there are at least five ones, in particular, the four in $$$s[5, 8]$$$ and the extra one in the third position.

This motivates Alice's strategy as well. Suppose that $$$n \lt 2\cdot k$$$. Alice would like to make sure that Bob is losing value from his moves. Notice that every substring of length $$$k$$$ includes the element $$$s_k$$$. So, after Bob's first turn, we have that $$$s_k=1$$$. Now, a winning strategy for Alice is to leave $$$s_k=1$$$ until her last turn, and otherwise choose any $$$k$$$ arbitrary ones to flip. This guarantees that after every round, $$$\mathrm{cnt}$$$ decreases, because Alice flips $$$k$$$ ones, whereas Bob flips at most $$$k-1$$$ zeros, since $$$a_k$$$ is already one. Since $$$\mathrm{cnt}$$$ is nonnegative, finite, and decreasing, it must eventually reach zero.

For example, consider $$$n=8$$$ and $$$k=5$$$. Suppose that before Alice's turn, $$$s=01111101$$$. Then we have that $$$\mathrm{cnt}=6$$$. Alice wants to choose any $$$5$$$ ones to flip, except for $$$s_5$$$. So she chooses to flip $$$s_2$$$, $$$s_3$$$, $$$s_4$$$, $$$s_6$$$, and $$$s_8$$$. Now, before Bob's turn, $$$s=00001000$$$. But any substring of length $$$5$$$ includes $$$s_5$$$, so Bob can only flip at most $$$4$$$ zeros. Suppose he chooses $$$s[2, 6]$$$. Then after his turn, we have that $$$s=01111100$$$. During this round, the value of $$$\mathrm{cnt}$$$ decreased from $$$6$$$ to $$$5$$$, as desired.

#include <bits/stdc++.h>
using namespace std;
 
void solve(){
    int n, k, cnt = 0;
    string s;
    cin >> n >> k >> s;
    for(char c : s)
        if(c == '1')
            cnt++;
    cout << (cnt <= k || n < 2*k ? "Alice" : "Bob") << '\n';
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while(t--) solve();
}

• Excellent problem
• Good problem
• Average problem
• Bad problem
• Horrible problem

• Trivial problem
• Easy problem
• Average problem
• Hard problem
• Impossible problem

Let $$$\mathrm{mex}$$$ be the original $$$\mathrm{MEX}$$$ of $$$a$$$. Clearly we cannot increase $$$\mathrm{MEX}(a)$$$ by removing elements. So, for every $$$0\leq i\leq \mathrm{mex}$$$, let's try to determine, for which $$$k$$$ can we make $$$\mathrm{MEX}(a) = i$$$?

We must have $$$i\leq n-k$$$, since the $$$\mathrm{MEX}$$$ of an array cannot be greater than its size. Furthermore, we must have $$$\mathrm{freq}(i) \leq k$$$, since we have to remove all instances of $$$i$$$ in order to make it the $$$\mathrm{MEX}$$$ of $$$a$$$.

Now, we claim that these are the only constraints. Indeed, suppose that $$$0\leq i\leq \mathrm{mex}$$$, $$$i\leq n-k$$$, and $$$\mathrm{freq}(i) \leq k$$$. We want to choose $$$n-k$$$ elements to keep. Since $$$i\leq \mathrm{mex}$$$, every element smaller than $$$i$$$ is in $$$a$$$, and since $$$i\leq n-k$$$, we can first choose one instance of every element less than $$$i$$$. Now, the $$$\mathrm{MEX}$$$ of our chosen elements is $$$i$$$, so we just need to choose the rest of the elements without affecting the $$$\mathrm{MEX}$$$. We can just choose elements arbitrarily, as long as we don't choose $$$i$$$. Since $$$\mathrm{freq}(i) \leq k$$$, we have enough spare elements to reach our $$$n-k$$$ quota without needing to choose $$$i$$$.

Let's maintain a set of elements which can be $$$\mathrm{MEX}(a)$$$ after removing $$$k$$$ elements. As $$$k$$$ increases, how does this set change? If we compare the set from $$$k-1$$$ to $$$k$$$, we now have that the value $$$n-(k-1)$$$ is no longer legal, since $$$n-(k-1) \gt n-k$$$, so let's erase this element from our set. Furthermore, any elements with frequency $$$k$$$ might now be legal, so let's add them to our set as long as they are $$$\leq \min(\mathrm{mex}, n-k)$$$. Then we output the size of our set.

#include <bits/stdc++.h>
using namespace std;
 
void solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    map<int, int> freq;
    set<int> excl;
    for(int i=0; i<=n; i++)
        excl.insert(i);
    for(int i=0; i<n; i++){
        cin >> a[i];
        freq[a[i]]++;
        excl.erase(a[i]);
    }
    map<int, vector<int>> invfreq;
    for(pair<int, int> p : freq)
        invfreq[p.second].push_back(p.first);
    int mex = *excl.begin();
    set<int> vals;
    vals.insert(mex);
    for(int k=0; k<=n; k++){
        vals.erase(n-k+1);
        for(int i : invfreq[k])
            if(i <= min(mex, n-k))
                vals.insert(i);
        cout << vals.size() << (k != n ? ' ' : '\n');
    }
}
 
int main(){
    int t;
    cin >> t;
    while(t--) solve();
}

Let $$$\mathrm{ans}_k$$$ be the number of possible values of $$$\mathrm{MEX}(a)$$$ after removing $$$k$$$ elements from $$$a$$$. Now, let $$$\mathrm{diff}$$$ be the difference array of $$$\mathrm{ans}$$$; that is, $$$\mathrm{diff}_k = \mathrm{ans}_k - \mathrm{ans}_{k-1}$$$. Then for all $$$0\leq i\leq \mathrm{mex}$$$, we have that $$$\mathrm{MEX}(a)$$$ can be $$$i$$$ if and only if $$$\mathrm{freq}(i) \leq k \leq n-i$$$. So we increment $$$\mathrm{diff}_{\mathrm{freq}(i)}$$$ and decrement $$$\mathrm{diff}_{n-i+1}$$$. Finally, we can reconstruct $$$\mathrm{ans}$$$ by taking the prefix sums of $$$\mathrm{diff}$$$.

#include <bits/stdc++.h>
using namespace std;
 
void solve(){
    int n;
    cin >> n;
    vector<int> a(n), ans(n+1), diff(n+2);
    map<int, int> freq;
    for(int i=0; i<n; i++){
        cin >> a[i];
        freq[a[i]]++;
    }
    for(int i=0; i<=n; i++){
        diff[freq[i]]++;
        diff[n-i+1]--;
        if(!freq[i])
            break;
    }
    for(int k=0; k<=n; k++){
        ans[k] = (k ? ans[k-1] : 0) + diff[k];
        cout << ans[k] << (k != n ? ' ' : '\n');
    }
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while(t--) solve();
}

• Excellent problem
• Good problem
• Average problem
• Bad problem
• Horrible problem

• Trivial problem
• Easy problem
• Average problem
• Hard problem
• Impossible problem

Let's first find out which values must be fixed points. Clearly if $$$i$$$ is relatively prime to every $$$1\leq j\leq n$$$ with $$$j\neq i$$$, then $$$i$$$ must be a fixed point. This occurs when $$$i=1$$$, or when $$$i$$$ is prime and $$$2\cdot i \gt n$$$, because the smallest number that is not relatively prime to prime $$$i$$$ is $$$2\cdot i$$$.

Now, let's try to construct $$$p$$$ such that these are the only fixed points. Consider the cycle decomposition of $$$p$$$. If we can ensure that all elements in a cycle, excluding the cycle $$$(1)$$$, share a common divisor greater than $$$1$$$, then $$$p$$$ is good.

Notice that a fixed point corresponds to a cycle of length $$$1$$$. So we want as few cycles of length $$$1$$$ as possible. The prime $$$i$$$ are the most restrictive. Let's pair all prime $$$i$$$ with $$$2\cdot i$$$, if possible. Now, none of the primes $$$\leq \frac{n}{2}$$$ are fixed points. For the remaining composites, we have a lot more freedom. We can insert them into the cycle with any one of their prime factors; now, the composites are also not fixed points. Then all cycles share a common divisor, namely, the prime in that cycle, so $$$p$$$ is good.

One systematic way to do this is to partition the elements from $$$1$$$ to $$$n$$$ based on their largest prime divisor. Then, indeed, all of the elements in the cycle containing prime $$$i$$$ are divisible by $$$i$$$, and $$$2\cdot i$$$ has largest prime factor $$$i$$$, so if $$$2\cdot i \leq n$$$, it will be in the cycle containing $$$i$$$.

#include <bits/stdc++.h>
using namespace std;
 
vector<bool> comp(1e5+1);
vector<int> primes;
 
void sieve(){
    for(int i=2; i*i<=1e5; i++)
        if(!comp[i])
            for(int j=i*i; j<=1e5; j+=i)
                comp[j] = true;
    for(int i=2; i<=1e5; i++)
        if(!comp[i])
            primes.push_back(i);
}
 
void solve(){
    int n;
    cin >> n;
    vector<int> p(n+1);
    for(auto it = primes.rbegin(); it != primes.rend(); ++it){
        vector<int> cycle;
        for(int i=*it; i<=n; i+=*it)
            if(!p[i])
                cycle.push_back(i);
        for(int i=0; i<cycle.size(); i++)
            p[cycle[i]] = cycle[(i+1) % cycle.size()];
    }
    for(int i=1; i<=n; i++)
        if(!p[i])
            p[i] = i;
    for(int i=1; i<=n; i++)
        cout << p[i] << (i != n ? ' ' : '\n');
}
 
int main(){
    sieve();
    int t;
    cin >> t;
    while(t--) solve();
}

• Excellent problem
• Good problem
• Average problem
• Bad problem
• Horrible problem

• Trivial problem
• Easy problem
• Average problem
• Hard problem
• Impossible problem

Let's first try to answer a query of type 2 in $$$O(n)$$$. We want to set $$$a_1$$$ as small as possible. Then we want to set $$$a_2$$$ to the smallest value which is $$$\geq a_1$$$. We continue to choose elements greedily, selecting the smallest legal value $$$a_i$$$ which is $$$\geq a_{i-1}$$$. If at any point there are no legal values, the answer is $$$\texttt{NO}$$$. Otherwise, the answer is $$$\texttt{YES}$$$.

Now, let's try to characterize what values we can change $$$a_i$$$ into. Clearly $$$a_i\pmod{\gcd(k, m)}$$$ is invariant across operations.

Next, we claim that all values less than $$$m$$$ which are congruent to $$$a_i\pmod{\gcd(k, m)}$$$ are reachable.

First, let's consider the case where $$$\gcd(k, m) = 1$$$. Then we can set $$$a_i := a_i + 1\pmod m$$$ by applying the operation onto $$$a_i$$$, $$$x$$$ times, where $$$x$$$ is the modular multiplicative inverse of $$$k\pmod m$$$. By repeatedly adding $$$1$$$, we can set $$$a_i$$$ to any value.

Next, let's consider the case where $$$\gcd(k, m) \gt 1$$$. Then, if we imagine dividing $$$k$$$ and $$$m$$$ by $$$\gcd(k, m)$$$, we fall into the previous case; that is, we can set $$$a_i := a_i + \gcd(k, m)\pmod m$$$ by applying the operation onto $$$a_i$$$, $$$x$$$ times, where $$$x$$$ is the modular multiplicative inverse of $$$\frac{k}{\gcd(k, m)}\pmod{\frac{m}{\gcd(k, m)}}$$$. By repeatedly adding $$$\gcd(k, m)$$$, we can set $$$a_i$$$ to any value which falls into the same congruence class $$$\bmod{\gcd(k, m)}$$$.

Let's try simulating the greedy process, where we repeatedly choose the smallest value which lies in the same congruence class $$$\bmod \gcd(k, m)$$$. Then if we have $$$a_n \lt m$$$, we can sort the array.

However, we want to represent the array in a way such that we can update $$$a_i$$$ quickly, and check the end-result of $$$a_n$$$ after our greedy process quickly. Let $$$\mathrm{diff}$$$ be the difference array of $$$a$$$; that is, $$$\mathrm{diff}_i = a_i - a_{i-1}$$$ (for convenience, we will define $$$a_0 = 0$$$). Then, by telescoping sum, we have that $$$a_n$$$ is the sum of the elements of the difference array; that is, $$$a_n = (a_n - a_{n-1}) + (a_{n-1} - a_{n-2}) + \dots + (a_2 - a_1) + (a_1 - a_0)$$$.

Now, notice that $$$\mathrm{diff}_i$$$ is invariant $$$\bmod{\gcd(k, m)}$$$, and we also must have that $$$\mathrm{diff}_i$$$ is nonnegative for $$$a$$$ to be nondecreasing. So let's maintain the sum of the elements of the difference array, where each element is taken $$$\bmod{\gcd(k, m)}$$$, for each $$$k$$$. Then this is the final value of $$$a_n$$$ after simulating the greedy process. This is quick to update, since only two elements of the difference array are changed with each update.

Finally, we observe that $$$\gcd(k, m)$$$ is always a divisor of $$$m$$$, so we only have to maintain and update $$$d(m)$$$ different values. This allows us to answer queries in $$$O(d(m))$$$ time.

#include <bits/stdc++.h>
using namespace std;
 
int mod(int a, int m){
    return (a % m + m) % m;
}
 
void solve(){
    int n, m, q, op, i, x, k;
    cin >> n >> m >> q;
    vector<int> a(n+1);
    for(int i=1; i<=n; i++)
        cin >> a[i];
    map<int, long long> ans;
    for(int i=1; i*i<=m; i++)
        if(!(m % i)){
            ans[i] = 0;
            ans[m/i] = 0;
        }
    for(pair<int, int> p : ans)
        for(int i=1; i<=n; i++)
            ans[p.first] += mod(a[i] - a[i-1], p.first);
    while(q--){
        cin >> op;
        if(op == 1){
            cin >> i >> x;
            for(pair<int, int> p : ans){
                ans[p.first] += mod(x - a[i-1], p.first) - mod(a[i] - a[i-1], p.first);
                if(i != n)
                    ans[p.first] += mod(a[i+1] - x, p.first) - mod(a[i+1] - a[i], p.first);
            }
            a[i] = x;
        }
        else{
            cin >> k;
            cout << (ans[__gcd(k, m)] < m ? "YES" : "NO") << '\n';
        }
    }
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while(t--) solve();
}

Imagine putting all of the numbers from $$$0$$$ to $$$m-1$$$ in a grid, where each row is of size $$$\gcd(k, m)$$$. For example, if $$$k=8$$$ and $$$m=12$$$, our grid would look as follows:

Then observe that by applying operations, we can reach any element in the same column. Consider simulating the greedy process. Then we want to choose the lowest row possible; that is, we want to move up in the grid as infrequently as possible.

Notice that we only have to move up in the grid if $$$a_i \pmod{\gcd(k, m)} \lt a_{i-1} \pmod{\gcd(k, m)}$$$, because then we cannot stay in the same row. We want to move up in the grid $$$ \lt \frac{m}{\gcd(k, m)}$$$ times. So let's maintain the number of times we are forced to move up in the grid, for each $$$k$$$. This is quick to update, since when we update $$$a_i$$$, we only have to compare it to the two adjacent values.

Finally, we observe that $$$\gcd(k, m)$$$ is always a divisor of $$$m$$$, so we only have to maintain and update $$$d(m)$$$ different values. This allows us to answer queries in $$$O(d(m))$$$ time.

#include <bits/stdc++.h>
using namespace std;
 
void solve(){
    int n, m, q, op, i, x, k;
    cin >> n >> m >> q;
    vector<int> a(n+1);
    for(int i=1; i<=n; i++)
        cin >> a[i];
    map<int, int> ans;
    for(int i=1; i*i<=m; i++)
        if(!(m % i)){
            ans[i] = 0;
            ans[m/i] = 0;
        }
    for(pair<int, int> p : ans)
        for(int i=1; i<=n; i++)
            ans[p.first] += (a[i] % p.first < a[i-1] % p.first);
    while(q--){
        cin >> op;
        if(op == 1){
            cin >> i >> x;
            for(pair<int, int> p : ans){
                ans[p.first] += (x % p.first < a[i-1] % p.first) - (a[i] % p.first < a[i-1] % p.first);
                if(i != n)
                    ans[p.first] += (a[i+1] % p.first < x % p.first) - (a[i+1] % p.first < a[i] % p.first);
            }
            a[i] = x;
        }
        else{
            cin >> k;
            cout << (ans[__gcd(k, m)] < m / __gcd(k, m) ? "YES" : "NO") << '\n';
        }
    }
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while(t--) solve();
}

• Excellent problem
• Good problem
• Average problem
• Bad problem
• Horrible problem

• Trivial problem
• Easy problem
• Average problem
• Hard problem
• Impossible problem