↵
I will try to correct mistakes and expand editorial. Russian editorial will be published later.↵
↵
[problem:675A]↵
↵
Firstly, in case $c = 0$ we should output
↵
[problem:675A]↵
↵
Во-первых, в случае $c = 0$ мы должны вывести YES
↵
↵
So answer is
↵
Поэтому ответ YES
↵
↵
↵
↵
↵
↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
int main() {↵
int a, b, c;↵
cin >> a >> b >> c;↵
↵
if (c == 0) {↵
if (a == b) cout << "YESn";↵
else cout << "NOn";↵
} else {↵
if ((b - a) % c == 0 && (b - a) / c >= 0) cout << "YESn";↵
else cout << "NOn";↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
↵
x a y↵
↵
b m c↵
↵
z d w↵
↵
So, let's find answer with fixed number in the center and then multiply answer by $n$.↵
↵
Let's iterate over all possible $x$.↵
Sums of each subsquare $2\times 2$ are the same so
Поэтому мы можем найти ответ с фиксированным числом в центре и потом домножить его на $n$.↵
↵
Переберем все возможные $x$.↵
Суммы в каждом квадрате $2\times 2$ одинаковы, поэтому $x + b + a + m = y + c + a + m$
↵
↵
↵
Also we can solve this problem in $O(1)$.↵
↵
↵
↵
↵
Это было решение за $O(n)$. Существует также решение за $O(1)$.↵
↵
↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <iostream>↵
↵
using namespace std;↵
↵
int main() {↵
int n, a, b, c, d;↵
cin >> n >> a >> b >> c >> d;↵
↵
long long ans = 0;↵
for (int x = 1; x <= n; x++) {↵
int y = x + b - c;↵
int z = x + a - d;↵
int w = a + y - d;↵
if (1 <= y && y <= n && 1 <= z && z <= n && 1 <= w && w <= n) {↵
ans++;↵
}↵
}↵
ans *= n;↵
↵
cout << ans << endl;↵
}↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
↵
Sum of all $a_i$ equals to zero.↵
↵
We can divide array into parts of consecutive elements with zero sum.↵
If part has length $l$ we can use all pairs of neighbours in operations and make all numbers be equal to zero with $l - 1$ operations.↵
↵
So, if we sum number of operations in each part we get $ans = n - k$ where $k$ is number of parts.↵
We should maximize $k$ to get the optimal answer.↵
↵
One of the part consists of some prefix and probably some suffix. Each of other parts is subarray of $a$.↵
↵
Let's calculate prefix sums. Each part has zero sum so prefix sums before each part-subarray are the same.↵
↵
So we can calculate $f$ — number of occurencies of the most frequent number in prefix sums and answer will be equal to $n - f$.↵
↵
Bonus: how to hack solutions with overflow?↵
↵
Сумма всех чисел в массиве равна нулю.↵
↵
Мы можем разделить массив на части с нулевой суммой, состоящие из последовательных элементов↵
(первый и последний элемент считаются последовательными).↵
Если часть имеет длину $l$, то мы можем обнулить ее с помощью $l - 1$ операции.↵
↵
Следовательно, если мы сложим количество операций, то получим, что ответ равен $n - k$, где $k$ — количество частей.↵
Для того, чтобы ответ был минимальным, мы должны максимизировать $k$.↵
↵
Одна из частей состоит из префикса и, возможно, суффикса массива. Остальные части являются подмассивами.↵
↵
Давайте посчитаем префиксные суммы. Заметим, что префиксные суммы перед частями-подмассивами равны между собой,↵
так как сумма чисел в каждой части равна нулю.↵
↵
Следовательно, ответ равен $n - f$, где $f$ — количество вхождений самого частого элемента среди префиксных сумм.↵
↵
Бонус: как взламывать решения с переполнением?↵
↵
↵
↵
↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
int main() {↵
ios_base::sync_with_stdio(false); cin.tie(0);↵
↵
int n;↵
cin >> n;↵
map<long long, int> d;↵
long long sum = 0;↵
int ans = n - 1;↵
for (int i = 0; i < n; i++) {↵
int t;↵
cin >> t;↵
sum += t;↵
d[sum]++;↵
ans = min(ans, n - d[sum]);↵
}↵
↵
cout << ans << endl;↵
}↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
[problem:675D]↵
↵
↵
Let we should add number $x$. Find numbers $l < x < r$ which were added earlier, $l$ is maximal possible, $r$ is minimal possible↵
(all will be similar if only one of this numbers exists). We can find them for example with
↵
Пусть сейчас мы должны добавить число $x$. Найдем ранее добавленные числа $l < x < r$ такие, что $l$ максимально возможное,↵
а $r$ минимально возможное. Если только одно из этих чисел существует, то рассуждения почти не меняются.↵
Мы можем найти $l$ и $r$, например, с помощью std::set
↵
We should keep sorted tree traversal (it's property of BST). So $x$ must be right child of vertex with $l$ or ↵
left child of vertex with $r$.↵
↵
Let $l$ hasn't right child and $r$ hasn't left child. Hence lowest common ancestor (lca) of
↵
Мы должны сохранять отсортированный обход дерева, так как это свойство двоичного дерева поиска.↵
Поэтому $x$ должно быть правым потомком вершины $l$ или левым потомком вершины $r$.↵
↵
Пусть $l$ не имеет правого потомка и $r$ не имеет левого потомка. Тогда наименьший общий предок $l$
So $l$ has right child or $r$ has left child and we know exactly which of them will be parent of $x$.↵
↵
That's all. Time complexity is
Получается противоречие, поэтому $l$ имеет правого потомка или $r$ имеет левого потомка.↵
Следовательно, мы точно знаем, кто из них станет предком $x$.↵
↵
Это всё. Сложность решения $O(n \log n)$.↵
↵
↵
↵
↵
↵
↵
↵
~~~~~↵
#include <iostream>↵
#include <set>↵
#include <map>↵
↵
using namespace std;↵
↵
int main() {↵
ios_base::sync_with_stdio(false); cin.tie(0);↵
↵
set<int> numbers;↵
map<int, int> left;↵
map<int, int> right;↵
↵
int n, v;↵
cin >> n >> v;↵
numbers.insert(v);↵
for (int i = 0; i < n - 1; i++) {↵
cin >> v;↵
auto it = numbers.upper_bound(v);↵
int result;↵
if (it != numbers.end() && left.count(*it) == 0) {↵
left[*it] = v;↵
result = *it;↵
} else {↵
it--;↵
right[*it] = v;↵
result = *it;↵
}↵
numbers.insert(v);↵
cout << result;↵
if (i == n - 2) cout << 'n';↵
else cout << ' ';↵
}↵
}↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
[problem:675E]↵
↵
Also let
↵
Пусть $dp_i$
↵
$dp_{n - 1} = 0$↵
↵
$dp_i = dp_m - (a_i - m) + n - i - 1$
We can find $m$ with segment tree or binary indexed tree or sparse table.↵
↵
Now answer equals to sum of all $dp_i$.↵
↵
↵
↵
↵
Ответ равен сумме всех $dp_i$.↵
↵
↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
const int maxn = 1 << 18;↵
pair<int, int> tree[maxn * 2];↵
↵
void build(const vector<int> &a, int n) {↵
for (int i = 0; i < n; i++) tree[maxn + i] = {a[i], i};↵
for (int i = maxn - 1; i > 0; i--)↵
tree[i] = max(tree[i * 2], tree[i * 2 + 1]);↵
}↵
↵
int get(int l, int r) {↵
pair<int, int> ans{-1, -1};↵
for (l += maxn, r += maxn + 1; l < r; l >>= 1, r >>= 1) {↵
if (l & 1) ans = max(ans, tree[l++]);↵
if (r & 1) ans = max(ans, tree[--r]);↵
}↵
return ans.second;↵
}↵
↵
int main() {↵
ios_base::sync_with_stdio(false); cin.tie(0);↵
↵
int n;↵
cin >> n;↵
vector<int> a(n);↵
a[n - 1] = n - 1;↵
for (int i = 0; i < n - 1; i++) {↵
cin >> a[i];↵
a[i]--;↵
}↵
↵
build(a, n);↵
vector<long long> dp(n);↵
long long ans = 0;↵
dp[n - 1] = 0;↵
for (int i = n - 2; i >= 0; i--) {↵
int m = get(i + 1, a[i]);↵
dp[i] = dp[m] - (a[i] - m) + n - i - 1;↵
ans += dp[i];↵
}↵
↵
cout << ans << 'n';↵
}↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
