Решение D:

Заметим, что если мы увеличиваем $$$z[i]$$$ на 1 (и при этом $$$z[i]$$$ < $$$m$$$), то количество строк со значением 1 или не меняется, или увеличивается на 1(так как все элементы во всех столбцах различны).

Из этого следует, что существует ответ такого вида: $$$[m, m, ...., m, x, 0, ...,0]$$$.

Теперь чтобы найти такой ответ, достаточно бинарного поиска по длине префикса $$$m$$$, а затем бинарного поиска по $$$x$$$.

Асимптотика $$$O(nm * (log(m) + log(n)))$$$

Решение C:

Сначала для каждого элемента предпочитаем индекс первого элемента справа равного ему. Это можно делать например с помощью unordered_map.

Теперь для каждого элемента будем искать в скольких отрезках длины $$$1$$$, $$$2$$$, $$$3$$$.. он будет самым правым из чисел равных ему на отрезке. Очевидно, что если мы такое посчитаем для каждого элемента и каждой длины то мы получим ответ на задачу.

Рассмотрим пример

У нас массив {$$$2$$$, $$$3$$$, $$$1$$$, $$$4$$$, $$$6$$$, $$$4$$$, $$$3$$$, $$$3$$$, $$$1$$$, $$$57$$$} и мы рассматриваем первую единицу. Для каждой длины посчитаем в скольких отрезков этой длины содержится наше число

Колво: $$$1$$$ $$$2$$$ $$$3$$$ $$$3$$$ $$$3$$$ $$$3$$$ $$$2$$$ $$$1$$$ $$$0$$$ $$$0$$$

Длина: $$$1$$$ $$$2$$$ $$$3$$$ $$$4$$$ $$$5$$$ $$$6$$$ $$$7$$$ $$$8$$$ $$$9$$$ $$$10$$$

Легко заметить что верхний массив для любого элемента и массива будет иметь вид {$$$1$$$ $$$2$$$ $$$3$$$ .... $$$x$$$ — $$$1$$$ $$$x$$$ $$$x$$$ $$$x$$$ ... $$$x$$$ $$$x$$$ $$$x$$$ — $$$1$$$ ... $$$3$$$ $$$2$$$ $$$1$$$} Это очевидным образом представляется в виде сумм и разностей арифметических прогрессий. Значит мы свели задачу к прибавлению арифметической прогрессии на отрезке. Эта задача может быть решена за линейное время.

Итоговая асимптотика: $$$O$$$($$$n$$$)

Другое (моё) решение C:

Давайте пойдем справа налево и будем поддерживать для каждого числа массива $$$1$$$ если число встречается впервые на данном суффиксе и $$$0$$$ иначе. Давайте посмотрим что у нас получится, если для всех суффиксов мы выпишем полученные последовательности $$$0$$$ и $$$1$$$ в таблицу. Например рассмотрим сэмпл (массив $$$1\,3\,2\,1\,2$$$):

Давайте заметим что $$$S_d$$$ это сумма на каком-то параллелограмме таблицы (мда). Для ясности, вот $$$S_3$$$ для нашего примера:

Ну, давайте посмотрим, как пересчитывается $$$S_{d+1}$$$ через $$$S_d$$$. Мы вычитаем верхнюю строку и добавляем справа диагональ. То есть примерно вот так (зеленое — удаляем, синее — добавляем):

Теперь, что нам надо сделать? Давайте посчитаем для каждого элемента, для каких длин $$$d$$$ он вносит вклад. Заметим, что элемент $$$i$$$ вносит вклад в длины не более $$$i$$$.

Кроме того, давайте посчитаем когда для этого элемента $$$1$$$ заменяется на $$$0$$$ (до этого момента во всех строках, в которые этот элемент входил, будет стоять $$$1$$$, а после — всегда $$$0$$$). Пусть это $$$when_i$$$ для $$$i$$$-ого элемента. Если же элемент до конца прохода будет первым на суффиксе среди равных ему, положим $$$when_i = -1$$$ (по сути это индекс ближайшего элемента равного ему, но стоящего левее). Тогда несложно заметить, что этот элемент вносит вклад во все длины не более $$$n - when_i$$$.

То есть нам нужно добавить, что элемент вносит вклад (увеличивает на 1) все длины от $$$1$$$ до $$$min(i, n - when_i)$$$, добавляясь как элемент на правой диагонали, прибавив $$$1$$$ на соответствующем отрезке. Это делается за линию префиксными суммами.

Теперь мы посчитали, по сути, для каждой длины сумму на последней диагонали. Теперь чтобы посчитать ответ для $$$S_d$$$, нужно в полученном массиве добавить к $$$d$$$-ому элементу $$$S_{d-1}$$$ и вычесть сумму на суффиксе длины $$$d$$$ (та самая верхняя строка). Первое мы уже посчитали, второе легко считается при проходе справа налево.

Снова другое решение на C (чем-то схожее с решением devid, если я случайно пересказал его, поправьте пж):
Заметим что все отрезки длины d состоят из какого-то отрезка d — 1 (в данном решении будет рассматривать, что это суффикc) и одного элемента слева.
Давайте подумаем как можно пересчитывать S(d) через S(d — 1):
По факту нам нужно просто не учитывать те элементы, которые уже были в d — 1, когды мы их добавили
Для этого давайте обозначим за next(i) = ближайщий справа элемент, равный a[i];
А pref(i) = количество различных на префиксе длины i;

Теперь S(d) = S(d — 1) — pref(d — 1) + кол-во элементов массива next от 0 до n — d — 1, больших d; pref(d — 1) мы вычитаем для того, чтобы не учитывать отрезок длины d — 1, являющий префиксом исходного массива(очевидно, что слева мы не можем добавить элементы). Считать мы его можем за n log n просто проходом сетом.

Как быстро считать третье слагаемое? Здесь я писал дд, мб можно что-то другое.
Давайте изначально добавим в дд все элементы массива next от 0 до n — 2.
Теперь будем искать кол-во элементов, больших 1 (можно просто сплитом);
После этого удаляем элемент на позиции n — 2;
Теперь ищем кол-во элементов, больших 2... Думаю алгоритм понятен.
Все значения записываем в массив. И теперь мы можем спокойно найти S(d) через S(d — 1)
S(0) = n, как база;

В этом году на Codeforces пишут 17 регионов. Вот результаты после первого тура: https://codeforces.net/spectator/ranklist/bbd85b80155bc7d5df6e5681729d7f27

Я пока не понял подробности, но меня попросили официально временно не публиковать эту ссылку. Извините, ссылка более недоступна.

Хабаровский край (классы: 11, 10) https://imcs.dvfu.ru/cats/main.pl?f=rank_table;cid=3033335;sid=;sites=1178986

Приморский край (классы:10, 11, 9, 10) https://imcs.dvfu.ru/cats/main.pl?f=rank_table;cid=3033335;sid=;sites=1175454

Камчатский край https://imcs.dvfu.ru/cats/main.pl?f=rank_table;cid=3033335;sid=;sites=1217892

Суммарная таблица по всем трём регионам за оба тура (11, 10, 9, 11, ?): https://imcs.dvfu.ru/cats/main.pl?f=rank_table;cache=1;clist=3033335,3033343;hide_ooc=1;hide_virtual=1;sid=

Элегантное (имхо) решение на С.

Пусть изначально все $$$S[i] = 0$$$, теперь найдём вклад каждого индекса в ответ.

Я утверждаю, что элемент $$$a[i]$$$ даёт вклад во все отрезки, в которых $$$i$$$ является первым вхождением этого элемента (иначе, впервые "открывает" этот элемент другой индекс, вклад принадлежит именно ему). Как это формализовать: все отрезки $$$[l, r]$$$, при $$$prev[a[i]] < l <= i$$$ и $$$i <= r < n$$$, нумерация с 0, $$$prev[x]$$$ — индекс предыдущего вхождения типа задания $$$x$$$.

Теперь понятно, как это делать за $$$O(n^3 log n)$$$, можно от лога избавиться если сжать координаты (отпадает необходимость в map).

Как это делать за квадрат? Давайте разберёмся, что же происходит. Мы итерируемся по $$$l$$$ от $$$prev[a[i]] + 1$$$ до $$$i$$$, включительно. На каждой итерации мы рассматриваем отрезки с правыми концами от $$$i$$$ до $$$n - 1$$$, крайние длины соответственно будут $$$i - l + 1$$$ и $$$n - i$$$. Это по сути, прибавление 1 на отрезке. Так как сначала идут все запросы, а потом нужно вывести значение, можно сделать прибавление за $$$O(1)$$$ — просто завести массив флажков $$$flag$$$, классический приём, кто не в курсе. Тогда для прибавления единицы на отрезке $$$[l, r]$$$, мы просто делаем flag[l]++ и flag[r + 1]--, потом уже проходимся по массиву, обновляем текущее значение на значение флажка в данном индексе, и это значение выходного массива $$$S$$$ в данном индексе.

До фулла отсюда недалеко. Заметим, что все увеличения флажков на 1 (при каком-то $$$i$$$) находятся в подряд идущих индексах (очевидно, так как мы итерируем $$$l$$$ по одному). А поэтому, можно взять самые кратчайшие длины для левейшего и правейшего $$$l$$$, а также соответственные максимальные длины. Для первых мы делаем запрос на увеличение 1 на отрезке массива флажков (это важно, не конечного массива!!), аналогично с последними, только увеличение на -1. После этого мы восстанавливаем значения флажков, и уже с их помощью достраиваем массив.

в D есть решение за O(nm), по каждой строке можно построить дерево где val[2n-1] корень,а x[i]ые — листья. Отсортируем подсчётом столбцы, пусть изначально все z[i] = 0, будем увеличивать z[0] на 1 пока z[0] < m, z[1] и тд когда z[i] увеличится на 1 лист в некотором дереве станет 1(до этого он был 0), пойдём по дереву от листа изменяя значения в вершинах до первой 1 или до первой вершины с op = and у которого другой потомок равен 0, если мы дошли до корня значить количество True увеличилось на 1. Будем делать так пока кол-во true не станет равно s. В итоге по каждому ребру дерева будет не > 1 прохода, Увеличений z[i] будет не > mn.

Мне за последние 30 минут стало немного страшно за завтра. Это было запланировано?

upd. в случае падения тестирующей системы, продлят ли нам тур на время крэша? если нет, что будут делать в такой ситуации?

upd2. Прошу прощения за панику, тур прошёл великолепно :)

Можете пожалуйста объяснить решение задачи B на полный балл

Ребят, 2 года назад на всерос брали примерно: 120 из 11, 80 из 10 и 60 из 9

1 год назад примерно всех по 80,с чем это связано?

Такое ощущение, что в этому году 10 классу может не хватить и 650 баллов для отбора

Решения второго дня:

Мои решения, насколько я понимаю, отличающиеся от авторских(?):

Предварительные результаты:

• Кабардино-Балкарская Республика — https://codeforces.net/spectator/ranklist/cda7adc997e0b21e292c6332f966b82b
• Сириус — https://codeforces.net/spectator/ranklist/e5c1bc69cdfaaadbaad57dd1d14a0251
• Смоленская область — https://codeforces.net/spectator/ranklist/f4372960785c92dd010e141bd5a3e440
• Новгородская область — https://codeforces.net/spectator/ranklist/3862bdccc8d90cf0f329e0a23476c029
• Томская область — https://codeforces.net/spectator/ranklist/19aa04d44d83435d754d09b241341ffe
• Тамбовская область — https://codeforces.net/spectator/ranklist/e849463d92af29ac8c79a77eeb462f49
• Кировская область — https://codeforces.net/spectator/ranklist/88a33abdbcb666566240877881d74e83
• Саратовская область — https://codeforces.net/spectator/ranklist/9390e7d75da9c102b4758942861d9a3f
• Пермский край — https://codeforces.net/spectator/ranklist/2a3a565eba7d71c48acc6ed322530e40
• Республика Саха (Якутия) — https://codeforces.net/spectator/ranklist/f0a0521c32c89fa1afb0a26361bb10f4
• Ямало-Ненецкий автономный округ — https://codeforces.net/spectator/ranklist/e1cd17b543bb2e3f311779b695fd9259
• Республика Мордовия — https://codeforces.net/spectator/ranklist/49d2dce62fad3671995788232931df4e
• Ростовская область — https://codeforces.net/spectator/ranklist/b4d17c543d2eff1e51ed1e051d677903
• Тюменская область — https://codeforces.net/spectator/ranklist/419cd8ce9a07549855b6fdb99c9fd84c
• Иркутская область — https://codeforces.net/spectator/ranklist/12152da153ba523be9fae53f833ba998
• Брянская область — https://codeforces.net/spectator/ranklist/99617a232c19aa860864603321695934
• Вологодская область — https://codeforces.net/spectator/ranklist/f34c48fefcf6d47c79943a6f1f7bbf84

А в Кемеровской области произошёл мем. Пошёл сильный снегопад и гибдд не разрешил детям ехать на автобусе в город, чтобы писать второй этап (дети для подготовки собираются в лагере за неделю до олимпиады). В итоге область пишет олимпиаду в понедельник с другими заданиями. Явно будут другие баллы, никаких равных условий. Дети будут сидеть в лагере еще два дня, откуда им взять еду и места жития, там же новые подъедут

Кто может объединить все результаты в одну табличку?

На московском сайте материалы выставили: https://olympiads.ru/moscow/2019-20/vsosh/region_start.shtml

Сюда свел оба дня многих регионов

https://docs.google.com/spreadsheets/d/1QrJ7RYvNthgGsyq1nE0DSziU402mloF6zusSIse1ypQ/edit#gid=574526530

Москвы естественно нет

Кто знает, когда будет дорешка?

UPD: кстати, такое решение может работать и за $$$O(n^2)$$$, если заранее посчитать до максимального $$$n$$$, $$$cnt[i][j]$$$ — количество делителей $$$i$$$, меньших $$$j$$$. Тогда можно совершать переходы в основной динамике за $$$O(1)$$$.

Результаты Ижевска: https://bacs.cs.istu.ru/

Как думаете какой проходной балл у 11 класса в этом году?

https://olympiads.ru/moscow/2019-20/vsosh/region_results.shtml москва

Результаты ЕКБ: https://docs.google.com/spreadsheets/d/1H21ygJthNHttLz7lKWJLFFmvsjyBXq-poen7mGceudU/edit?usp=sharing

Задачи доступны для дорешивания на Яндекс.Контесте:

• первый день
• второй день

Оба тура в Тренировках Codeforces:

• 2019-2020 Всероссийская олимпиада школьников по информатике, региональный этап, 1 тур
• 2019-2020 Всероссийская олимпиада школьников по информатике, региональный этап, 2 тур

UPD: Исправил доступ.

А какой проход будет примерно по 9 классу

Результаты новосибирской области https://drive.google.com/file/d/1SRlD5QcucDz_hQPmm-tkbEV5afForm_6/view?usp=sharing

а я зделал 1 и 5 задачки и куснул 3 на 22 балла

Официальные и окончательные результаты Челябинска: https://rcokio.ru/files/upload/olimp/vseros/itog_19-20/informatika.xlsx

Уже не знаю, насколько это актуально, но раз в "странных опросах" до сих пор обсуждают асимптотику к B2, представлю решение за $$$O(n \log ^2 n)$$$. Такую асимптотику можно получить несложной оптимизацией вышеописанного решения с ДП (достаточно только заметить, что полезных состояний для вычисления ответа всего $$$n \log n$$$).

Эта реализация позволяет получить ответ для $$$n = 4 \cdot 10^5$$$ за одну секунду:

#include<bits/stdc++.h>
#define int long long
using namespace std;
 
const int MAXN = 400001;
vector<int> divisors[MAXN];
 
int count_rect(int limit, int area, int x) {
    int ans = 0;
    for (auto i : divisors[area]) {
        if (i < limit) ans++;
    }
    return ans;
}
 
int count_s(int width, int k, int x) {
    if (k <= width) return 0;
    return count_s(width, k - width, x) + count_rect(width, k - width, x);
}
 
void fix(int x, int n, int &ans) {
    ans -= 2 * count_s(x, n, x);
    int free_area = x * x - n;
    for (int i = 2; i * i <= free_area; i++) {
        if (free_area % i == 0 && i < x && free_area / i < x) ans += 2 - (i * i == free_area);
    }
}
 
signed main() {
    int n, x;
    int ans = 0;
    cin >> n >> x;
    for (int i = 1; i < MAXN; i++) {
        for (int j = i; j < MAXN; j += i) divisors[j].push_back(i);
    }
    for (int i = 1; i <= n; i++) ans += count_s(i, n, x);
    if (x) fix(x, n, ans);
    cout << ans;
}

Результаты в республике Адыгея

Проходные баллы: 9: 543, 10: 607, 11: 644