Если для всех $$$i$$$ $$$(1 \leq i \leq n - 1)$$$ верно $$$|a_i - a_{i+1}| = 5$$$ или $$$|a_i - a_{i+1}| = 7$$$, ответ на задачу — "YES", иначе — "NO".

Сложность: $$$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";
    }
}

Заведем массив brand_cost длиной $$$k$$$ и заполним его так, что brand_cost[i] хранит стоимость всех бутылок бренда $$$i+1$$$. Затем отсортируем массив по невозрастанию и посчитаем сумму его первых min(n, k) элементов, что и будет ответом на задачу.

Сложность: $$$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;
}

При каждом запросе, чтобы отследить изменение наличия "1100" в строке, не обязательно проходить по всей строке — можно проверить только несколько соседних клеток.

Сначала наивным способом посчитаем $$$count$$$ — количество раз, которое "1100" встречается в $$$s$$$.

Далее для каждого из $$$q$$$ запросов будем обновлять $$$count$$$: рассмотрим подстроку $$$s[\max(1, i - 3); \min(i + 3, n)]$$$ до изменения $$$s_i$$$ и найдем $$$before$$$ — количество раз, которое "1100" встречается в ней. После этого обновим $$$s_i = v$$$ и аналогично найдем $$$after$$$ — количество раз, которое "1100" встречается в $$$s[\max(1, i - 3); \min(i + 3, n)]$$$ после применения запроса.

Таким образом, выполнив $$$count = count + (after - before)$$$, мы получим количество раз, которое "1100" встречается в $$$s$$$ после применения запроса. Если $$$count \gt 0$$$, ответ на запрос — "YES", иначе — "NO".

Сложность: $$$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();
}

Будем идти по всем слоям ковра, добавляя к ответу число встреченных записей $$$1543$$$ на каждом слое. Для этого можно итерироваться по, например, левым верхним клеткам каждого из слоев, имеющим вид $$$(i, i)$$$ для всех $$$i$$$ в диапазоне $$$[1, \frac{min(n, m)}{2}]$$$, после чего делать обход слоя наивным алгоритмом, записывая встреченные цифры в какой-нибудь массив. Затем пройдёмся по массиву и посчитаем вхождения $$$1543$$$ в этот слой. Также при обходе массива нужно учесть цикличность слоя, не забыв проверить возможные вхождения $$$1543$$$, содержащие стартовую клетку.

Сложность: $$$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();
}

Для любых целых неотрицательных чисел выполняется $$$a \leq a | b$$$, где $$$|$$$ — операция побитового "или".

После вычисления значений $$$b_{i,j}$$$ для всех стран и регионов, мы можем заметить, что для фиксированного региона $$$j$$$ значения $$$b_{i,j}$$$ возрастают с увеличением индекса $$$i$$$. Это происходит потому, что операция побитового "или" не может уменьшить число, а только увеличивает или оставляет его неизменным. Следовательно, мы можем использовать бинарный поиск для быстрого нахождения страны, которая соответствует заданным условиям.

Для каждого запроса и для каждого требования, если знак $$$o$$$ = "<", мы ищем первую страну, где $$$b_{i,r} \geq c$$$ (это будет первая страна, не удовлетворяющая условию). Если же знак $$$o$$$ = ">", мы ищем первую страну, где $$$b_{i,r} \leq c$$$. В обоих случаях мы можем использовать стандартный бинарный поиск для нахождения индекса. Если в результате проверок осталась хотя бы одна страна, которая удовлетворяет всем требованиям, выбираем страну с наименьшим номером.

Сложность: подсчёт значений $$$O(n \cdot k)$$$, обработка каждого запроса с помощью бинарного поиска $$$O(m \log n)$$$, итого $$$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");
	}
}

Обратите внимание на основание модуля

Можем ли мы быстро вычислить XOR на отрезке $$$[l, r]$$$?

Рекомендуем также красивый разбор задачи от ne_justlm!

Введём обозначение $$$\DeclareMathOperator{\XOR}{XOR}\XOR(l, r) = l \oplus (l+1) \oplus \dots \oplus r$$$ .

Первое, что приходит в голову при прочтении условия, это что мы можем вычислить XOR всех чисел на отрезке $$$(0, x)$$$ за $$$O(1)$$$ по следующей формуле:

Тогда $$$\XOR(l, r)$$$ можно найти как $$$\XOR(0, r) \oplus \XOR(0, l-1)$$$.

Теперь заметим, что для ответа нам достаточно научиться за $$$O(1)$$$ находить XOR всех неинтересных на отрезке: тогда мы сможем сделать XOR со всем отрезком и получить XOR уже всех интересных чисел.

Основание модуля, равное степени двойки, выбрано не случайно: нам достаточно "сжать" $$$l$$$ и $$$r$$$ в $$$2^i$$$ раз таким образом, чтобы в полученном диапазоне лежали все неинтересные числа, сдвинутые на $$$i$$$ битов право. Тогда вычислив $$$\XOR(l', r')$$$ мы получим в точности искомый XOR неинтересных чисел, также сдвинутый на $$$i$$$ битов вправо. Тогда, чтобы найти эти оставшиеся младшие $$$i$$$ битов, нам достаточно найти количество неинтересных чисел на отрезке $$$[l, r]$$$. Если оно будет нечётным, эти $$$i$$$ битов будут равны $$$k$$$, поскольку все они равны $$$k \mod 2^i$$$, а значит имеют одинаковые $$$i$$$ младших битов, равные собственно $$$k$$$, а значит их XOR нечетное число раз будет также равен $$$k$$$.

В противном случае младшие $$$i$$$ битов ответа будут равны $$$0$$$, так как мы сделали XOR чётное число раз. Количество неинтересных чисел на отрезке можно вычислить похожим с $$$\XOR(l, r)$$$ способом, а именно найти их количество на отрезках $$$[0, r]$$$ и $$$[0, l-1]$$$ и вычесть второе из первого. Количество чисел, равных $$$k$$$ оп модулю $$$m$$$ и не превышающих $$$r$$$ вычисляется как $$$\left\lfloor \frac{r - k}{m} \right\rfloor$$$.

Сложность решения по времени: $$$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;
}

Рассмотрели ли вы те случаи, когда $$$a \oplus b \oplus c = 0$$$?

Предположим, что вы точно уверены в том, что хотя бы одно потерянное число расположено на некотором отрезке $$$[le, ri]$$$. Можете ли вы выбрать такое значение $$$mid$$$, при котором по запросам xor {le} {mid} и xor {mid + 1} {ri} вы сможете однозначно понять, на каком из отрезков ($$$[le, mid]$$$ или $$$[(mid + 1), ri]$$$) лежит хотя бы одно потерянное число, даже если оба эти запроса вернут $$$0$$$?

Для начало отметим, что для любого числа $$$x$$$ выполняется $$$x \oplus x = 0$$$. Поэтому запрашивая xor l r, вы получите побитовый XOR только тех номеров томов, которые находятся в библиотеке в единственном экземпляре (в рамках запроса $$$l$$$ и $$$r$$$, конечно). Также отметим, что для двух попарно различных чисел $$$x$$$ и $$$y$$$ всегда выполняется $$$x \oplus y \neq 0$$$.

Изначально наша цель — определить наибольший бит максимального из потерянных чисел. Для этого можно пройтись по битам, начиная от наибольшего значащего бита в n. Для каждого $$$i$$$-го бита будем запрашивать xor {2^i} {min(2^(i + 1) - 1, n)}. Заметим, что у всех чисел на этом интервале $$$i$$$-й бит равен единице. Тогда если мы получили результат не равный нулю, то этот бит является искомым наибольшим битом максимального из потерянных чисел. Если же мы получили результат равный нулю, то этот бит гарантированно не присутсвует в ни одном из чисел, т.е. все три числа меньше, чем $$$2^i$$$.

Докажем это. Если бы у нас находились одно или два числа на запрошенном интервале, то их XOR был бы не равен $$$0$$$ (см. первый абзац). Если же все три числа расположены на этом интервале, то XOR их $$$i$$$-го бита равен $$$1 \oplus 1 \oplus 1 = 1$$$, и следовательно XOR самих чисел также отличен от $$$0$$$.

Теперь, когда мы знаем наибольший бит $$$i$$$ искомого числа, мы можем найти это число любой реализацией бинарного поиска внутри интервала $$$[2^i; min(2^{i + 1} - 1, n)]$$$. По ответу на любой запрос на каком-либо интервале внутри этого мы можем однозначно понять, присутствует ли наше число на этом интервале, или нет — доказательство аналогичное выше приведённому.

Первое число найдено. Второе число можно считать уже любым бинпоиском, так как XOR двух различных чисел всегда отличен от нуля. Главное не забывать "исключать" уже найденное число из полученного результата с помощью того же XOR-а. А третье число можно найти, запросив результат всего интервала от $$$1$$$ до $$$n$$$ и "исключив" из него уже найденные два числа.

Количество запросов: $$$\approx 2 \cdot \log n \approx 120 \lt 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();
}