If for all $$$i$$$ $$$(1 \leq i \leq n - 1)$$$ is true $$$|a_i - a_{i+1}| = 5$$$ or $$$|a_i - a_{i+1}| = 7$$$, the answer to the problem is “YES”, otherwise it is “NO”.

Complexity: $$$O(n)$$$

#include <bits/stdc++.h>
using namespace std;
 
bool solve(){
    int n;
    cin >> n;
    vector<int>a(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 1; i < n; i++) {
        if(abs(a[i] - a[i - 1]) != 5 && abs(a[i] - a[i - 1]) != 7) return false;
    }
    return true;
}
int main() {
    int t;
    cin >> t;
    while(t--){
        cout << (solve() ? "YES" : "NO") << "\n";
    }
}

Let's create an array brand_cost of length $$$k$$$ and fill it so that brand_cost[i] stores the cost of all bottles of brand $$$i+1$$$. Then sort the array by non-growing and calculate the sum of its first min(n, k) elements, which will be the answer to the problem.

Complexity: $$$O(k \cdot \log k)$$$

#include <bits/stdc++.h>
using namespace std;
 
void solve() {
  int n, k;
  cin >> n >> k;
  vector<int> brand_cost(k, 0);
  for (int i = 0; i < k; i++) {
    int b, c;
    cin >> b >> c;
    brand_cost[b - 1] += c;
  }
  sort(brand_cost.rbegin(), brand_cost.rend());
  long long ans = 0;
  for (int i = 0; i < min(n, k); i++) {
    ans += brand_cost[i];
  }
  cout << ans << '\n';
}
 
int main() {
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}

With each query, to track the change in the presence of “1100” in a row, you don't have to go through the entire row — you can check just a few neighboring cells.

First, in a naive way, let's count $$$count$$$ — the number of times “1100” occurs in $$$s$$$.

Then for each of $$$q$$$ queries we will update $$$count$$$: consider the substring $$$s[\max(1, i - 3); \min(i + 3, n)]$$$ before changing $$$s_i$$$ and find $$$before$$$ — the number of times that “1100” occurs in it. Then update $$$s_i = v$$$ and similarly find $$$after$$$ — the number of times that “1100” occurs in $$$s[\max(1, i - 3); \min(i + 3, n)]$$$ after applying the query.

Thus, by doing $$$count = count + (after - before)$$$, we get the number of times that “1100” occurs in $$$s$$$ after the query is applied. If $$$count > 0$$$, the answer to the query is “YES”, otherwise it is “NO”.

Complexity: $$$O(|s| + q)$$$

#include <cstdio>
#include <cstring>

using namespace std;
typedef long long l;

char buf[1000000];
l n;

bool check_1100(l i) {
	if (i < 0) return false;
	if (i >= n - 3) return false;
	if (buf[i] == '1' && buf[i + 1] == '1' && buf[i + 2] == '0' && buf[i + 3] == '0') return true;
	return false;
}

void solve() {
	scanf("%s", buf);
	n = strlen(buf);
	l count = 0;
	for (l i = 0; i < n; i++)
		if (check_1100(i)) count++;
	
	l q; scanf("%lld", &q);
	while (q--) {
		l i, v; scanf("%lld %lld", &i, &v); i--;
		if (buf[i] != '0' + v) {
		    bool before = check_1100(i - 3) || check_1100(i - 2) || check_1100(i - 1) || check_1100(i);
		    buf[i] = '0' + v;
		    bool after = check_1100(i - 3) || check_1100(i - 2) || check_1100(i - 1) || check_1100(i);
		    count += after - before;
		}
		printf(count ? "YES\n" : "NO\n");
	}
}

int main() {
	l t; scanf("%lld", &t);
	while (t--) solve();
}

We will go through all layers of the carpet, adding to the answer the number of $$$1543$$$ records encountered on each layer. To do this, we can iterate over, for example, the top-left cells of each layer having the form $$$(i, i)$$$ for all $$$i$$$ in the range $$$[1, \frac{min(n, m)}{2}]$$$, and then traverse the layer with a naive algorithm, writing the encountered digits into some array. Then traverse the array and count the $$$1543$$$ occurrences in that layer. Also, when traversing the array, we should take into account the cyclic nature of the layer, remembering to check for possible occurrences of $$$1543$$$ containing a starting cell.

Complexity: $$$O(n \cdot m)$$$

#include <cstdio>

char a[1005][1005];
char layer[4005];

void solve() {
    int n, m; scanf("%d %d", &n, &m);
    for (int i = 0; i < n; ++i) scanf("%s", a[i]);
    
    int count = 0;
    for (int i = 0; (i + 1) * 2 <= n && (i + 1) * 2 <= m; ++i) {
        int pos = 0;
        for (int j = i; j < m - i; ++j) layer[pos++] = a[i][j];
        for (int j = i + 1; j < n - i - 1; ++j) layer[pos++] = a[j][m - i - 1];
        for (int j = m - i - 1; j >= i; --j) layer[pos++] = a[n - i - 1][j];
        for (int j = n - i - 2; j >= i + 1; --j) layer[pos++] = a[j][i];
        
        for (int j = 0; j < pos; ++j)
            if (layer[j] == '1' && layer[(j + 1) % pos] == '5' && layer[(j + 2) % pos] == '4' && layer[(j + 3) % pos] == '3')
                count++;
        
    }
    
    printf("%lld\n", count);
}
 
int main() {
    int t; scanf("%d", &t);
    while (t--) solve();
}

For any non-negative integers, $$$a \leq a | b$$$, where $$$|$$$ is the bitwise “or” operation.

After computing the values of $$$b_{i,j}$$$ for all countries and regions, we can notice that for a fixed region $$$j$$$, the values of $$$b_{i,j}$$$ increase as the index $$$i$$$ increases. This is because the bitwise “or” operation cannot decrease a number, but only increase or leave it unchanged. Hence, we can use binary search to quickly find the country that matches the given conditions.

For each query and for each requirement, if $$$o$$$ = “<”, we search for the first country where $$$b_{i,r} \geq c$$$ (this will be the first country that does not satisfy the condition). If sign $$$o$$$ = “>”, we look for the first country where $$$b_{i,r} \leq c$$$. In both cases, we can use standard binary search to find the index. If the checks leave at least one country that satisfies all the requirements, we choose the country with the lowest number.

Complexity: counting values $$$O(n\cdot k)$$$, processing each query using binary search $$$O(m \log n)$$$, total $$$O(n \cdot k + q \cdot m \cdot \log n)$$$.

#include <cstdio>
typedef long long l;

l ** arr;

int main() {
	l n, k, q; scanf("%lld %lld %lld", &n, &k, &q);
	
	arr = new l*[n];
	for (l i = 0; i < n; i++) arr[i] = new l[k];
	for (l i = 0; i < n; i++) for (l j = 0; j < k; j++) scanf("%lld", &arr[i][j]);
	
	for (l i = 1; i < n; i++) for (l j = 0; j < k; j++) arr[i][j] |= arr[i - 1][j];
	
	while (q--) {
		l m; scanf("%lld", &m);
		l left_pos = 0, right_pos = n - 1;
		while (m--) {
			l r, c; char o; scanf("%lld %c %lld", &r, &o, &c); r--;
			if (o == '<') {
				l le = -1, ri = n, mid;
				while (le + 1 != ri) {
					mid = (le + ri) / 2;
					if (arr[mid][r] < c) le = mid;
					else ri = mid;
				}
				if (le < right_pos) right_pos = le;
			} else {
				l le = -1, ri = n, mid;
				while (le + 1 != ri) {
					mid = (le + ri) / 2;
					if (arr[mid][r] <= c) le = mid;
					else ri = mid;
				}
				if (ri > left_pos) left_pos = ri;
			}
		}
		if (left_pos <= right_pos) printf("%lld\n", left_pos + 1);
		else printf("-1\n");
	}
}

Note the base of the module

Can we quickly compute XOR on the segment $$$[l, r]$$$?

We also recommend the beautiful tutorial by justlm!

Let us introduce the notation $$$\DeclareMathOperator{\XOR}{XOR}\XOR(l, r) = l \oplus (l+1) \oplus \dots \oplus r$$$ .

The first thing that comes to mind when reading the condition is that we can compute XOR of all numbers on the segment $$$(0, x)$$$ for $$$O(1)$$$ by the following formula:

Then $$$\XOR(l, r)$$$ can be found as $$$\XOR(0, r) \oplus \XOR(0, l-1)$$$.

Now note that for the answer we only need to learn for $$$O(1)$$$ to find XOR of all uninteresting on the segment: then we can do XOR with the whole segment and get XOR of all interesting numbers already.

The base of the modulus, equal to the degree of two, is not chosen by chance: we only need to “compress” $$$l$$$ and $$$r$$$ by $$$2^i$$$ times in such a way that the resulting range contains all uninteresting numbers shifted $$$i$$$ bits to the right. Then computing $$$\XOR(l', r')$$$ we get exactly the desired XOR of uninteresting numbers, also shifted $$$i$$$ bits to the right. Then, to find these remaining lower $$$i$$$ bits, we just need to find the number of uninteresting numbers on the segment $$$[l, r]$$$. If it is odd, these $$$i$$$ bits will be equal to $$$k$$$, since they are all equal to $$$k \mod 2^i$$$, and so have the same $$$i$$$ minor bits equal to $$$k$$$ proper, and so their XOR an odd number of times will also be equal to $$$k$$$.

Otherwise, the lower $$$i$$$ bits of the answer will be $$$0$$$, since we have done XOR an even number of times. The number of uninteresting numbers on the segment can be calculated in a similar way to $$$\XOR(l, r)$$$, namely find their number on the segments $$$[0, r]$$$ and $$$[0, l-1]$$$ and subtract the latter from the former. The number of numbers equal to $$$k$$$ modulo $$$m$$$ and not exceeding $$$r$$$ is calculated as $$$\left\lfloor \frac{r - k}{m} \right\rfloor$$$.

Time complexity of the solution: $$$O(\mathit{\log r})$$$.

#include <iostream>
using namespace std;
#define int uint64_t
#define SPEEDY std::ios_base::sync_with_stdio(0); std::cin.tie(0); std::cout.tie(0);
 
int xor_0_n(int n) {
    int rem = n % 4;
    if (rem == 0) {
        return n;
    }
    if (rem == 1) {
        return 1;
    }
    if (rem == 2) {
        return n + 1;
    }
    return 0;
}
 
int xor_range(int l, int r) {
    return xor_0_n(r) ^ xor_0_n(l - 1);
}
 
int32_t main() {
    int t;
    cin >> t;
    while (t--) {
        int l, r, i, k;
        cin >> l >> r >> i >> k;
        int highBits = xor_range((l - k + (1 << i) - 1) >> i, (r - k) >> i) << i;
        int lowBits = k * (((r - k) / (1 << i) - (l - k - 1) / (1 << i)) & 1);
        cout << (xor_range(l, r) ^ highBits ^ lowBits) << '\n';
    }
    return 0;
}

Have you considered the cases where $$$a \oplus b \oplus c = 0$$$?

Suppose you are certain that at least one lost number is located on some segment $$$[le, ri]$$$. Can you choose a value $$$mid$$$ such that the queries xor {le} {mid} and xor {mid + 1} {ri} you can unambiguously understand on which of the segments ($$$[le, mid]$$$ or $$$[(mid + 1), ri]$$$) lies at least one lost number, even if both of these queries return $$$0$$$?

To begin with, we note that for any number $$$x$$$, $$$x \oplus x = 0$$$ is satisfied. Therefore, by querying xor l r, you will get bitwise XOR of only those volume numbers that are in the library in a single copy (within the scope of querying $$$l$$$ and $$$r$$$, of course). Also note that for two pairwise distinct numbers $$$x$$$ and $$$y$$$, $$$x \oplus y \neq 0$$$ is always satisfied.

Initially, our goal is — to determine the largest bit of the maximum of the lost numbers. To do this, we can go through the bits starting from the largest significant bit in n. For each $$$i$$$-th bit, we will ask xor {2^i} {min(2^(i + 1) - 1, n)}. Note that all numbers on this interval have $$$i$$$-th bit equal to one. Then if we get a result not equal to zero, then this bit is the desired largest bit of the maximum of the lost numbers. If we get a result equal to zero, then this bit is guaranteed not to be present in any of the numbers, i.e. all three numbers are less than $$$2^i$$$.

Let's prove it. If we had one or two numbers on the requested interval, their XOR would not be $$$0$$$ (see the first paragraph). If all three numbers are on this interval, then the XOR of their $$$i$$$-th bit is $$$1 \oplus 1 \oplus 1 = 1$$$, and hence the XOR of the numbers themselves is also different from $$$0$$$.

Now that we know the largest bit $$$i$$$ of the desired number, we can find this number by any realization of binary search inside the interval $$$[2^i; \min(2^{i + 1} - 1, n)]$$$. By the answer to any query on any interval within that interval, we can unambiguously know whether our number is present on that interval or not — the proof is similar to the one above.

The first number is found. The second number can be found using any bin search, since XOR of two different numbers is always different from zero. The main thing is not to forget to “exclude” the already found number from the obtained result using the same XOR. And the third number can be found by requesting the result of the whole interval from $$$1$$$ to $$$n$$$ and “excluding” the already found two numbers from it.

Number of requests: $$$\approx 2 \cdot \log n \approx 120 < 150$$$

#include <cstdio>
typedef long long l;

l n, num1, num2;

l req(l le, l ri, l num) {
    if (le > n) return 0;
    if (ri > n) ri = n;
    
    printf("xor %lld %lld\n", le, ri); fflush(stdout);
    l res; scanf("%lld", &res);
    
    if (num > 1 && le <= num1 && num1 <= ri) res ^= num1;
    if (num > 2 && le <= num2 && num2 <= ri) res ^= num2;
    return res;
}

void solve() {
    scanf("%lld", &n); num1 = 0; num2 = 0;
    l start = 1LL << (63 - __builtin_clzll(n));

    for (l i = start; i > 0; i >>= 1) {
        l res = req(num1 | i, num1 | (i * 2 - 1), 1);
        if (res) num1 |= i;
    }

    for (l i = start; i > 0; i >>= 1) {
        l res = req(num2 | i, num2 | (i * 2 - 1), 2);
        if (res) num2 |= i;
    }
    
    printf("ans %lld %lld %lld\n", num1, num2, req(1, n, 3));
    fflush(stdout);
}

int main() {
    l t; scanf("%lld", &t);
    while (t--) solve();
}