Если заметите неточности или ошибки, сообщите личным сообщением.
Div2A Раздача мороженого
Автор идеи: cdkrot
Подготовил задачу: ch_egor
В задаче требовалось просто реализовать то, что было сказано в условии.
Если у вас не получилось, то возможно вы забыли использовать 64-битные типы данных, или сделали какую-то ошибку.
Код правильного решения:
C++ code#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cassert>
#include <algorithm>
#include <iomanip>
#include <ctime>
#include <cmath>
#include <bitset>
#pragma comment(linker, "/STACK:256000000")
using namespace std;
typedef long long int int64;
typedef long double double80;
const int INF = (1 << 29) + 5;
const int64 LLINF = (1ll << 59) + 5;
const int MOD = 1000 * 1000 * 1000 + 7;
const int MAX_N = 1005;
int n, x, sad;
int64 answer;
int main()
{
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
scanf("%d %d\n", &n, &x);
answer = x;
sad = 0;
int cur;
char type;
for (int i = 0; i < n; ++i)
{
scanf("%c %d\n", &type, &cur);
if (type == '+')
{
answer += cur;
}
else if (answer >= cur)
{
answer -= cur;
}
else
{
++sad;
}
}
cout << answer << " " << sad << "\n";
fclose(stdin);
fclose(stdout);
return 0;
}
Python codeimport sys
def main():
n, answer = map(int, sys.stdin.readline().split())
sad = 0
for i in range(n):
type_of, cur = sys.stdin.readline().split()
cur = int(cur)
if type_of == "+":
answer += cur
elif answer >= cur:
answer -= cur
else:
sad += 1
sys.stdout.write(str(answer) + " " + str(sad))
main()
Div2B Зверинец маленькой разбойницы
Автор идеи: ch_egor
Подготовил задачу: ch_egor
Нам нужно отсортировать массив достаточно странными действиями, а именно — поменять местами элементы с четными и нечетными индексами на подотрезке четной длины. Заметим, что мы можем поменять 2 соседних элемента местами, просто выполнив наше действие обмена для подотрезка длины 2, содержащего эти элементы. Так же заметим, что n ≤ 100, а позволенно делать 20 000 действий, следовательно, мы можем написать любую квадратичную сортировку, которая меняет соседние элементы на каждой итерации (пузырьковую сортировку например).
Асимптотика O(n2)
C++ code#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cassert>
#include <algorithm>
#include <iomanip>
#include <ctime>
#include <cmath>
#include <bitset>
#pragma comment(linker, "/STACK:256000000")
using namespace std;
typedef long long int int64;
typedef long double double80;
const int INF = (1 << 29) + 5;
const int64 LLINF = (1ll << 59) + 5;
const int MOD = 1000 * 1000 * 1000 + 7;
const int MAX_N = 105;
int n;
int arr[MAX_N];
int main()
{
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
scanf("%d", &n);
for (int i = 0; i < n; ++i)
{
scanf("%d", &arr[i]);
}
for (int i = n - 1; i > 0; --i)
{
for (int j = 0; j < i; ++j)
{
if (arr[j] > arr[j + 1])
{
swap(arr[j], arr[j + 1]);
printf("%d %d\n", j + 1, j + 2);
}
}
}
fclose(stdin);
fclose(stdout);
return 0;
}
Python coden = int(input())
arr = list(map(int, input().split()))
for i in range(n - 1, 0, -1):
for j in range(i):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
print(j + 1, j + 2)
Бонус: Кто-нибудь умеет искать минимальное по длине решение данной задачи? Если да, то за какую сложность?
Div2C Разбойничьи часы/Div1A Разбойничьи часы
Автор идеи: cdkrot
Подготовил задачу: themikemikovi4
В этой задаче есть очень важное ограничение, а именно, используется семеричная система счисления! Давайте посчитаем сколько всего цифр отображается одновременно на циферблате часов и назовем cnt. Если cnt больше чем 7, то ответ, очевидно, 0. Если же cnt не больше 7, то переберем все возможные варианты выбора cnt цифр из 7 и в каждом варианте переберем все перестановки.
В зависимости от реализации получаем O(BASE BASEBASE), O(BASEBASE) или O(BASE BASE!), где BASE = 7.
Та же заметим, что в случае, когда cnt ≤ 7 мы можем просто 2 циклами перебрать час от 0 до n - 1 и минуту от 0 до m - 1 и проверить каждое время за O(cnt).
В худшем случае это отработает за O(BASE BASEBASE).
C++ code// Copyright (C) 2016 Sayutin Dmitry.
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License as
// published by the Free Software Foundation; version 3
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
// You should have received a copy of the GNU General Public License
// along with this program; If not, see <http://www.gnu.org/licenses/>.
#include <iostream>
#include <vector>
#include <stdint.h>
#include <algorithm>
#include <set>
#include <map>
#include <array>
#include <queue>
#include <stack>
#include <functional>
#include <utility>
#include <string>
#include <assert.h>
#include <iterator>
using std::cin;
using std::cout;
using std::cerr;
using std::vector;
using std::map;
using std::array;
using std::set;
using std::string;
using std::pair;
using std::make_pair;
using std::min;
using std::abs;
using std::max;
using std::sort;
using std::generate;
using std::min_element;
using std::max_element;
template <typename T>
T input() {
T res;
cin >> res;
return res;
}
int main() {
std::iostream::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
size_t n, m;
cin >> n >> m;
size_t len1 = 1, len2 = 1;
for (size_t a = 7; a < n; a *= 7)
len1 += 1;
for (size_t b = 7; b < m; b *= 7)
len2 += 1;
size_t ans = 0;
if (len1 + len2 <= 7)
for (size_t i = 0; i != n; ++i)
for (size_t j = 0; j != m; ++j) {
vector<size_t> used(7, 0);
for (size_t a = i, k = 0; k != len1; a /= 7, ++k)
used[a % 7] += 1;
for (size_t b = j, k = 0; k != len2; b /= 7, ++k)
used[b % 7] += 1;
if (*std::max_element(used.begin(), used.end()) <= 1)
++ans;
}
cout << ans << "\n";
return 0;
}
Python codeBASE = 7
def itov(x):
digits = []
if x == 0:
digits.append(0)
while x > 0:
digits.append(x % BASE)
x //= BASE
digits.reverse()
return digits
def gen(pos = 0, minute = False, smaller = False):
max_val = max_minute if minute else max_hour
if pos >= len(max_val):
if minute:
return 1
else:
return gen(0, True)
else:
ans = 0
for digit in range(BASE):
if not used[digit] and (smaller or digit <= max_val[pos]):
used[digit] = True
ans += gen(pos + 1, minute, smaller or digit < max_val[pos])
used[digit] = False
return ans
n, m = map(int, input().split())
n -= 1
m -= 1
used = [False] * BASE
max_hour = itov(n)
max_minute = itov(m)
print(gen())
Бонус: Предположим система счисления не фиксированная, а произвольная. Решить задачу при n ≤ 109, m ≤ 109, BASE ≤ 109. Можете ли вы сделать это за ?
Div2D Кай и снежинки/Div1B Кай и снежинки
Автор идеи: cdkrot
Подготовили задачу: ch_egor, cdkrot
Данная задача имеет несколько решений.
Решение от cdkrot:
Рассмотрим кандидатов на центроид поддерева вершины v. Очевидно, что размер поддерева центроида должен составлять хотя бы размера поддерева вершины v. Выберем из таких вершин вершину с минимальным размером поддерева. Если мы удалим эту вершину, то останется часть поддерева, связная с v размером не больше исходного поддерева и несколько других, размер каждой из которых тоже будет не более половины размера исходного поддерева. Следовательно мы нашли центроид. Чтобы быстро искать такую вершину выпишем эйлеров обход дерева и будем использовать двумерное дерево отрезков.
Асимптотика
C++ code// Copyright (C) 2016 Sayutin Dmitry.
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License as
// published by the Free Software Foundation; version 3
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
// You should have received a copy of the GNU General Public License
// along with this program; If not, see <http://www.gnu.org/licenses/>.
#include <iostream>
#include <vector>
#include <stdint.h>
#include <algorithm>
#include <set>
#include <map>
#include <array>
#include <queue>
#include <stack>
#include <functional>
#include <utility>
#include <string>
#include <assert.h>
#include <iterator>
using std::cin;
using std::cout;
using std::cerr;
using std::vector;
using std::map;
using std::array;
using std::set;
using std::string;
using std::pair;
using std::make_pair;
using std::min;
using std::abs;
using std::max;
using std::sort;
using std::generate;
using std::min_element;
using std::max_element;
template <typename T>
T input() {
T res;
cin >> res;
return res;
}
const size_t MAXN = (1 << 19);
vector<size_t> graph[MAXN];
vector<pair<size_t, size_t>> segm[2 * MAXN - 1];
#define time TIME_FUCKLIBC
pair<size_t, size_t> times[MAXN];
size_t time = 0;
size_t sizes[MAXN];
void dfs(size_t v) {
size_t sz = 1;
times[v].first = time++;
for (size_t u: graph[v]) {
dfs(u);
sz += sizes[u];
}
times[v].second = time;
segm[MAXN - 1 + times[v].first].emplace_back(sz, v);
sizes[v] = sz;
}
void buildseg(size_t node, size_t L, size_t R) {
if (L != R - 1) {
size_t mid = L + (R - L) / 2;
buildseg(2 * node + 1, L, mid);
buildseg(2 * node + 2, mid, R);
segm[node].resize(segm[2 * node + 1].size() + segm[2 * node + 2].size());
std::merge(segm[2 * node + 1].begin(), segm[2 * node + 1].end(), segm[2 * node + 2].begin(), segm[2 * node + 2].end(), segm[node].begin());
}
}
pair<size_t, size_t> lowerb(size_t node, size_t L, size_t R, size_t rl, size_t rr, pair<size_t, size_t> minval) {
if (rl <= L and R <= rr) {
auto it = std::lower_bound(segm[node].begin(), segm[node].end(), minval);
if (it == segm[node].end())
return make_pair(SIZE_MAX, SIZE_MAX);
else
return *it;
}
if (R <= rl or rr <= L)
return make_pair(SIZE_MAX, SIZE_MAX);
size_t mid = L + (R - L) / 2;
return min(lowerb(2 * node + 1, L, mid, rl, rr, minval)
,lowerb(2 * node + 2, mid, R, rl, rr, minval));
}
int main() {
std::iostream::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
size_t n, q;
cin >> n >> q;
for (size_t i = 1; i != n; ++i)
graph[input<size_t>() - 1].push_back(i);
dfs(0);
buildseg(0, 0, MAXN);
for (size_t i = 0; i != q; ++i) {
size_t v = input<size_t>() - 1;
cout << lowerb(0, 0, MAXN, times[v].first, times[v].second, make_pair((sizes[v] + 1) / 2, 0)).second + 1 << "\n";
}
return 0;
}
Так же можно насчитать ответы для всех поддеревьев за один dfs используя данную идею — будем использовать std::set по паре (размер поддерева, номер вершины) и в каждой вершине сливать сеты, полученые при запуске от детей. Таким образом мы получим ответы для всех вершин и нам остается только вывести ответы на запросы.
Асимптотика
C++ code// Copyright (C) 2016 Sayutin Dmitry.
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License as
// published by the Free Software Foundation; version 3
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
// You should have received a copy of the GNU General Public License
// along with this program; If not, see <http://www.gnu.org/licenses/>.
#include <iostream>
#include <vector>
#include <stdint.h>
#include <algorithm>
#include <set>
#include <map>
#include <array>
#include <queue>
#include <stack>
#include <functional>
#include <utility>
#include <string>
#include <assert.h>
#include <iterator>
using std::cin;
using std::cout;
using std::cerr;
using std::vector;
using std::map;
using std::array;
using std::set;
using std::string;
using std::pair;
using std::make_pair;
using std::min;
using std::abs;
using std::max;
using std::sort;
using std::generate;
using std::min_element;
using std::max_element;
template <typename T>
T input() {
T res;
cin >> res;
return res;
}
set<pair<size_t, size_t>> solve(const vector<vector<size_t>>& graph, vector<size_t>& ans, size_t v) {
set<pair<size_t, size_t>> cur;
for (size_t u: graph[v]) {
auto ch = solve(graph, ans, u);
if (not (ch.size() < cur.size()))
std::swap(ch, cur);
for (auto elem: ch)
cur.insert(elem);
}
size_t sz = cur.size() + 1;
cur.emplace(sz, v);
ans[v] = cur.lower_bound(make_pair((sz + 1) / 2, 0))->second;
return std::move(cur);
}
int main() {
std::iostream::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
size_t n, q;
cin >> n >> q;
vector<vector<size_t>> graph(n);
for (size_t i = 1; i != n; ++i)
graph[input<size_t>() - 1].push_back(i);
vector<size_t> ans(n, SIZE_MAX);
solve(graph, ans, 0);
for (size_t i = 0; i != q; ++i)
cout << ans[input<size_t>() - 1] + 1 << "\n";
return 0;
}
Решение от ch_egor:
Решим для всех поддеревьев. Пусть решаем задачу для какого-то поддерева, решив задачу для всех его детей. Выберем самого тяжёлого сына. Заметим, что центроид этого сына при некотором подъёме перейдёт в наш центроид. Промоделируем подъём. Таким образом мы получим ответы для всех вершин и нам остается только вывести ответы на запросы.
Асимптотика O(n + q)
C++ code#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cassert>
#include <algorithm>
#include <iomanip>
#include <ctime>
#include <cmath>
#include <bitset>
#pragma comment(linker, "/STACK:256000000")
using namespace std;
typedef long long int int64;
typedef long double double80;
const int INF = (1 << 29) + 5;
const int64 LLINF = (1ll << 59) + 5;
const int MOD = 1000 * 1000 * 1000 + 7;
const int MAX_N = 300 * 1000 + 5;
const int MAX_Q = 300 * 1000 + 5;
int n, q;
vector<int> graph[MAX_N];
int size_of[MAX_N];
int prev_of[MAX_N];
int big_subtree[MAX_N];
int centroid[MAX_N];
bool is_centroid_of_subtree(int v, int c)
{
return ((size_of[v] - size_of[c]) * 2 <= size_of[v] && big_subtree[c] * 2 <= size_of[v]);
}
void dfs_calc(int v, int p)
{
big_subtree[v] = 0;
size_of[v] = 1;
prev_of[v] = p;
for (int i = 0; i < graph[v].size(); ++i)
{
dfs_calc(graph[v][i], v);
size_of[v] += size_of[graph[v][i]];
big_subtree[v] = max(big_subtree[v], size_of[graph[v][i]]);
}
}
void dfs_centroid(int v)
{
if (size_of[v] == 1)
{
centroid[v] = v;
}
else
{
int ptr = 0;
for (int i = 0; i < graph[v].size(); ++i)
{
dfs_centroid(graph[v][i]);
if (size_of[graph[v][ptr]] < size_of[graph[v][i]])
{
ptr = i;
}
}
int c = centroid[graph[v][ptr]];
while (!is_centroid_of_subtree(v, c))
{
c = prev_of[c];
}
centroid[v] = c;
}
}
int main()
{
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
scanf("%d %d", &n, &q);
int v;
for (int i = 0; i < n - 1; ++i)
{
scanf("%d", &v);
graph[v - 1].push_back(i + 1);
}
dfs_calc(0, 0);
dfs_centroid(0);
for (int i = 0; i < q; ++i)
{
scanf("%d", &v);
printf("%d\n", centroid[v - 1] + 1);
}
fclose(stdin);
fclose(stdout);
return 0;
}
Div2E Оптимальная точка/Div1C Оптимальная точка
Автор идеи: cdkrot
Подготовил задачу: cdkrot
Пару слов о тернарном поиске. Тернарный поиск работает слишком долго.
Асимптотика работы тернарного поиска , где n = 105, а v = 1018.
Решение.
1) Давайте сделаем бинпоиск по ответу.
2) От каждой из данных точек отложим область подходящих точек (на расстоянии ≤ mid).
3) Пересечём области и проверим на пустоту.
Области будут иметь форму правильных октаэдров, и каждую из них можно описать системой линейных неравенств следующего вида:
(Получить данные уравнения можно расписав условие того, что манхэттанское расстояние ≤ mid)
.. ≤ x + y + z ≤ ..
.. ≤ - x + y + z ≤ ..
.. ≤ x - y + z ≤ ..
.. ≤ x + y - z ≤ ..
Где вместо .. стоят какие-то числа.
Пересечением множества таких систем будет система такого же вида, поэтому остаётся научится проверять существование решений у такой системы.
Сделаем замену:
a = - x + y + z
b = x - y + z
c = x + y - z
Тогда:
x + y + z = a + b + c
x = (b + c) / 2
y = (a + c) / 2
z = (a + b) / 2
Итого имеем систему:
.. ≤ a ≤ ..
.. ≤ b ≤ ..
.. ≤ c ≤ ..
.. ≤ a + b + c ≤ ..
Нам нужно проверить есть ли решение у такой системы в целых числах, при этом числа a, b, c должны быть одной чётности (чтобы конечные x, y, z тоже были целыми).
Как избавится от условия на одинаковую чётность? Давайте переберём какой чётности должны быть a, b, c (2 варианта).
Сделаем замену a = 2a' + r, b = 2b' + r, c = 2c' + r, где r = 0 или r = 1. Подставим, приведём, и получим систему такого же вида, но без обременения по поводу чётности.
Оставшаяся система легко решается жадно (Сначала набираем a, b, c по минимуму, а затем, в случае необходимости, потихоньку повышаем).
Итого асиптотика решения .
C++ code// Copyright (C) 2016 Sayutin Dmitry.
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License as
// published by the Free Software Foundation; version 3
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
// You should have received a copy of the GNU General Public License
// along with this program; If not, see <http://www.gnu.org/licenses/>.
#include <iostream>
#include <vector>
#include <stdint.h>
#include <algorithm>
#include <set>
#include <map>
#include <array>
#include <queue>
#include <stack>
#include <functional>
#include <utility>
#include <string>
#include <assert.h>
#include <iterator>
using std::cin;
using std::cout;
using std::cerr;
using std::vector;
using std::map;
using std::array;
using std::set;
using std::string;
using std::pair;
using std::make_pair;
using std::min;
using std::abs;
using std::max;
using std::sort;
using std::generate;
using std::min_element;
using std::max_element;
template <typename T>
T input() {
T res;
cin >> res;
return res;
}
struct coord {
int64_t x;
int64_t y;
int64_t z;
};
struct equation {
pair<int64_t, int64_t> S;
pair<int64_t, int64_t> a;
pair<int64_t, int64_t> b;
pair<int64_t, int64_t> c;
};
vector<coord> list;
equation operator+(const equation& e1, const equation& e2) {
equation res;
res.S = {max(e1.S.first, e2.S.first), min(e1.S.second, e2.S.second)};
res.a = {max(e1.a.first, e2.a.first), min(e1.a.second, e2.a.second)};
res.b = {max(e1.b.first, e2.b.first), min(e1.b.second, e2.b.second)};
res.c = {max(e1.c.first, e2.c.first), min(e1.c.second, e2.c.second)};
return res;
}
coord get_solution(const equation& eq) {
if ((eq.S.first > eq.S.second)
or (eq.a.first > eq.a.second)
or (eq.b.first > eq.b.second)
or (eq.c.first > eq.c.second))
return coord {INT64_MAX, INT64_MAX, INT64_MAX};
if ((eq.a.first + eq.b.first + eq.c.first > eq.S.second)
or (eq.a.second + eq.b.second + eq.c.second < eq.S.first))
return coord {INT64_MAX, INT64_MAX, INT64_MAX};
coord res;
res.x = eq.a.first;
res.y = eq.b.first;
res.z = eq.c.first;
int64_t delta = max(int64_t(0), eq.S.first - res.x - res.y - res.z);
res.x += min(delta, eq.a.second - eq.a.first);
delta -= min(delta, eq.a.second - eq.a.first);
res.y += min(delta, eq.b.second - eq.b.first);
delta -= min(delta, eq.b.second - eq.b.first);
res.z += min(delta, eq.c.second - eq.c.first);
delta -= min(delta, eq.c.second - eq.c.first);
assert(delta == 0);
return res;
}
int64_t DIV2(int64_t arg) {
return (arg - (arg & 1)) / 2;
}
coord can(int64_t MAXANS) {
equation eq;
eq.S = eq.a = eq.b = eq.c = {INT64_MIN, INT64_MAX};
for (const coord& crd: list) {
equation nw;
nw.S = { crd.x + crd.y + crd.z - MAXANS, crd.x + crd.y + crd.z + MAXANS};
nw.a = {-crd.x + crd.y + crd.z - MAXANS, -crd.x + crd.y + crd.z + MAXANS};
nw.b = { crd.x - crd.y + crd.z - MAXANS, crd.x - crd.y + crd.z + MAXANS};
nw.c = { crd.x + crd.y - crd.z - MAXANS, crd.x + crd.y - crd.z + MAXANS};
eq = eq + nw;
}
for (int64_t r = 0; r <= 1; ++r) {
equation tr = eq;
tr.S.first = DIV2(tr.S.first - 3 * r + 1);
tr.a.first = DIV2(tr.a.first - r + 1);
tr.b.first = DIV2(tr.b.first - r + 1);
tr.c.first = DIV2(tr.c.first - r + 1);
tr.S.second = DIV2(tr.S.second - 3 * r);
tr.a.second = DIV2(tr.a.second - r);
tr.b.second = DIV2(tr.b.second - r);
tr.c.second = DIV2(tr.c.second - r);
coord sol = get_solution(tr);
if (sol.x != INT64_MAX) {
coord ans;
ans.x = r + sol.y + sol.z;
ans.y = r + sol.x + sol.z;
ans.z = r + sol.x + sol.y;
return ans;
}
}
return coord {INT64_MAX, INT64_MAX, INT64_MAX};
}
int main() {
std::iostream::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
list.reserve(100000);
for (size_t T = input<size_t>(); T != 0; --T) {
list.resize(input<size_t>());
for (coord& crd: list)
cin >> crd.x >> crd.y >> crd.z;
int64_t L = -1; // definitely imposible
int64_t R = 3 * int64_t(1000 * 1000 * 1000) * int64_t(1000 * 1000 * 1000) + 10; // definitely possible
while (R - L > 1) {
int64_t M = L + (R - L) / 2;
if (can(M).x != INT64_MAX)
R = M;
else
L = M;
}
coord ans = can(R);
cout << ans.x << " " << ans.y << " " << ans.z << "\n";
}
return 0;
}
Бонус. У задачи есть много разных вариаций, например евклидово расстояние вместо манхэттенского, 2d вместо 3d, флоты вместо целых. Как решить эти вариации?
Div1D Кай и вечность
Авторы идеи: platypus179, Endagorion
Подготовил задачу: platypus179
Будем решать данную задачу методом сканирующей прямой. Будем идти по вертикалям слева на право и поддерживать массив, в котором на i вертикали в j ячейке будет храниться количество точек в квадрате с координатой левого нижнего угла (i, j). Сейчас это требует O(MAXCORD2) времени.
Заметим, что множество квадратов, которые содержат какую-то из закрашеных точек не очень велико, а именно — если точка имеет координаты (x, y), то множество левых нижних углов квадратов, содержащих ее задается так: {(a, b)|x - k + 1 ≤ a ≤ x, y - k + 1 ≤ b ≤ y}. Давайте рассматривать каждую точку (x, y) как 2 события:
Прибавить единицу на отрезке с y - k + 1 по y на вертикали x - k + 1 и отнять единицу на этом же отрезке на вертикали x + 1. Как же считать ответ при таком методе решения? Пусть мы обновляем значение ячейки на вертикали a, а до этого обновляли ее значением x на вертикали b. Прибавим к ответу для количества квадратов, содержащих x точек значение a - b. Мы можем реализовывать прибавление на отрезке в лоб и получим O(nk) на обработку всех событий, что укладывается по времени. Чтобы избавиться от O(MAXCORD) памяти, выпишем перед обработкой событий все интересующие нас координаты (их не более nk) и сожмем координаты в событиях. Это займет времени и O(nk) памяти. Теперь мы можем выполнить предыдущий пункт за O(nk) памяти.
Итоговая асимптотика времени и O(nk) памяти.
C++ code#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long ll;
#define NotANumber -1791791791
struct query {
int row, l, r; bool a;
int lbl, ubr;
query(int _row, int _l, int _r, bool _a) {row = _row; l = _l; r = _r; a = _a;}
bool operator<(const query& other) const {
return row < other.row;
}
};
int main() {
int n, k;
scanf("%d %d", &n, &k);
vector<pair<int, int> > points(n);
for (int i = 0; i < n; i++)
scanf("%d %d", &points[i].first, &points[i].second);
sort(points.begin(), points.end());
vector<int> xcoords;
for (int i = 0; i < n; i++) {
int st;
if (xcoords.empty())
st = points[i].first - k + 1;
else
st = max(xcoords.back() + 1, points[i].first - k + 1);
for (int j = st; j <= points[i].first; j++)
xcoords.push_back(j);
}
vector<query> qs;
for (int i = 0; i < n; i++) {
qs.push_back(query(points[i].second - k + 1, points[i].first - k + 1, points[i].first, 1));
qs.push_back(query(points[i].second + 1, points[i].first - k + 1, points[i].first, 0));
}
for (query & q : qs) {
q.lbl = lower_bound(xcoords.begin(), xcoords.end(), q.l) - xcoords.begin();
q.ubr = upper_bound(xcoords.begin(), xcoords.end(), q.r) - xcoords.begin();
}
int xcdssz = xcoords.size();
xcoords.clear();
xcoords.shrink_to_fit();
sort(qs.begin(), qs.end());
vector<int> vec(xcdssz, 0);
vector<int> lastchanged(xcdssz, NotANumber);
vector<ll> ans(n);
for (query q : qs) {
int lbl = q.lbl;
int ubr = q.ubr;
for (int i = lbl; i < ubr; i++) {
if (lastchanged[i] != NotANumber && vec[i] != 0) {
ans[vec[i] - 1] += q.row - lastchanged[i];
}
if (q.a)
vec[i]++;
else
vec[i]--;
lastchanged[i] = q.row;
}
}
for (int i = 0; i < n; i++)
printf("%lld ", ans[i]);
printf("\n");
return 0;
}
Бонус: времени и O(n) памяти.
C++ code#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cassert>
#include <algorithm>
#include <iomanip>
#include <ctime>
#include <cmath>
#include <bitset>
#pragma comment(linker, "/STACK:256000000")
using namespace std;
typedef long long int int64;
typedef long double double80;
const int INF = (1 << 29) + 5;
const int64 LLINF = (1ll << 59) + 5;
const int MOD = 1000 * 1000 * 1000 + 7;
const int MAX_N = 1000 * 100 + 5;
const int MAX_K = 305;
/** Interface */
inline int readChar();
template <class T = int> inline T readInt();
template <class T> inline void writeInt(T x);
inline void writeChar(int x);
inline void writeWord(const char *s);
inline void flush();
/** Read */
static const int buf_size = 20 * 1000 * 1000;
inline int getChar()
{
static char buf[buf_size];
static int len = 0, pos = 0;
if (pos == len)
pos = 0, len = fread(buf, 1, buf_size, stdin);
if (pos == len)
return -1;
return buf[pos++];
}
inline int readChar()
{
int c = getChar();
while (c <= 32)
c = getChar();
return c;
}
template <class T>
inline T readInt()
{
int s = 1, c = readChar();
T x = 0;
if (c == '-')
s = -1, c = getChar();
while ('0' <= c && c <= '9')
x = x * 10 + c - '0', c = getChar();
return s == 1 ? x : -x;
}
inline int64 readInt64()
{
int s = 1, c = readChar();
int64 x = 0;
if (c == '-')
s = -1, c = getChar();
while ('0' <= c && c <= '9')
x = x * 10 + c - '0', c = getChar();
return s == 1 ? x : -x;
}
/** Write */
static int write_pos = 0;
static char write_buf[buf_size];
inline void writeChar(int x)
{
if (write_pos == buf_size)
fwrite(write_buf, 1, buf_size, stdout), write_pos = 0;
write_buf[write_pos++] = x;
}
inline void flush()
{
if (write_pos)
fwrite(write_buf, 1, write_pos, stdout), write_pos = 0;
}
template <class T>
inline void writeInt(T x)
{
if (x < 0)
writeChar('-'), x = -x;
char s[24];
int n = 0;
while (x || !n)
s[n++] = '0' + x % 10, x /= 10;
while (n--)
writeChar(s[n]);
}
inline void writeInt64(int64 x)
{
if (x < 0)
writeChar('-'), x = -x;
char s[24];
int n = 0;
while (x || !n)
s[n++] = '0' + x % 10, x /= 10;
while (n--)
writeChar(s[n]);
}
inline void writeWord(const char *s)
{
while (*s)
writeChar(*s++);
}
struct point
{
int x;
int y;
};
struct ask
{
int l;
int r;
int ptr;
int type;
};
bool cmp(const ask &a, const ask &b)
{
return a.ptr < b.ptr;
}
int n, k;
point arr[MAX_N];
int cord[MAX_N * 2];
ask asks[MAX_N * 2];
int cord_len = 0;
int asks_len = 0;
bool have_prev_cord[MAX_N * 2];
bool have_prev_line[MAX_N * 2];
int last_of_cord[MAX_N * 2];
int last_of_line[MAX_N * 2];
int at_cord[MAX_N * 2];
int at_line[MAX_N * 2];
int64 answer[MAX_N];
int main()
{
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
n = readInt();
k = readInt();
for (int i = 0; i < n; ++i)
{
arr[i].x = readInt();
arr[i].y = readInt();
cord[cord_len++] = arr[i].x;
cord[cord_len++] = arr[i].x - k + 1;
}
sort(cord, cord + 2 * n);
cord_len = unique(cord, cord + 2 * n) - cord;
for (int i = 0; i < n; ++i)
{
asks[asks_len].l = lower_bound(cord, cord + cord_len, arr[i].x - k + 1) - cord;
asks[asks_len].r = lower_bound(cord, cord + cord_len, arr[i].x) - cord;
asks[asks_len].ptr = arr[i].y - k + 1;
asks[asks_len].type = 1;
++asks_len;
asks[asks_len].l = asks[asks_len - 1].l;
asks[asks_len].r = asks[asks_len - 1].r;
asks[asks_len].ptr = arr[i].y + 1;
asks[asks_len].type = -1;
++asks_len;
}
sort(asks, asks + asks_len, cmp);
memset(answer, 0, sizeof(answer));
memset(last_of_cord, 0, sizeof(last_of_cord));
memset(last_of_line, 0, sizeof(last_of_line));
memset(at_cord, 0, sizeof(at_cord));
memset(at_line, 0, sizeof(at_line));
memset(have_prev_cord, 0, sizeof(have_prev_cord));
memset(have_prev_line, 0, sizeof(have_prev_cord));
for (int i = 0; i < asks_len; ++i)
{
for (int j = asks[i].l; j <= asks[i].r; ++j)
{
if (!have_prev_cord[j])
{
have_prev_cord[j] = true;
last_of_cord[j] = asks[i].ptr;
at_cord[j] += asks[i].type;
}
else
{
answer[at_cord[j]] += asks[i].ptr - last_of_cord[j];
last_of_cord[j] = asks[i].ptr;
at_cord[j] += asks[i].type;
}
if (j != asks[i].r)
{
if (!have_prev_line[j])
{
have_prev_line[j] = true;
last_of_line[j] = asks[i].ptr;
at_line[j] += asks[i].type;
}
else
{
answer[at_line[j]] += 1ll * (cord[j + 1] - cord[j] - 1) * (asks[i].ptr - last_of_line[j]);
last_of_line[j] = asks[i].ptr;
at_line[j] += asks[i].type;
}
}
}
}
for (int i = 1; i <= n; ++i)
{
writeInt64(answer[i]);
writeChar(' ');
}
flush();
fclose(stdin);
fclose(stdout);
return 0;
}
Div1E Путешествие по царству Снежной королевы
Авторы идеи: cdkrot, GlebsHP
Подготовили задачу: ch_egor, cdkrot
Из-за моей (cdkrot) ошибки было возможно сдать задачу с решением за O(nm). Приношу свои извинения.
Мы предлагаем следующее решение:
Решим задачу используя метод разделяй и властвуй
. Для начала поднимем l до первого индекса, в котором s была упомянута. Также опустим r до того индекса, где упомянута вершина t Это не повлияет на ответ, но позволит сделать дальнейшее решение гораздо проще.
Посмотрим на запросы, для каждого запроса определим его расположение относительно центра массива рёбер. Либо он целиком справа, либо целиком слева, либо содержит середину. В первых двух случаях решим рекурсивно. (Предлагается написать функцию solve(reqs, l, r))
Решим третий случай. Предпосчитаем вспомогательные динамики:
dpr[i] = bitset вершин из которых можно попасть в вершину vi или ui, считая, что l = m и r = i.
dpl[i] = bitset вершин до которых можно дойти из vi или ui, считая, что l = i и r = m - 1
vi и ui — вершины i-го ребра.
Ответ на запрос будем "Yes" тогда и только тогда, когда: dpl[l][u] = true и dpr[r][u] = true для некоторого u.
Все вышесказаное нужно реализовать используя битовые операции. Итого время работы:
C++ code// Copyright (C) 2016 Sayutin Dmitry.
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License as
// published by the Free Software Foundation; version 3
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
// You should have received a copy of the GNU General Public License
// along with this program; If not, see <http://www.gnu.org/licenses/>.
#include <iostream>
#include <vector>
#include <stdint.h>
#include <algorithm>
#include <set>
#include <map>
#include <array>
#include <queue>
#include <stack>
#include <functional>
#include <utility>
#include <string>
#include <assert.h>
#include <iterator>
#include <bitset>
using std::cin;
using std::cout;
using std::cerr;
using std::vector;
using std::map;
using std::array;
using std::set;
using std::string;
using std::pair;
using std::make_pair;
using std::min;
using std::abs;
using std::max;
using std::sort;
using std::generate;
using std::min_element;
using std::max_element;
#define size_t uint32_t
struct Req {
size_t L;
size_t R;
size_t S;
size_t T;
size_t ID;
};
struct Edge {
size_t v;
size_t u;
size_t prev1;
size_t prev2;
size_t next1;
size_t next2;
};
const size_t MAXQ = 200000;
const size_t MAXN = 1000;
const size_t MAXM = 200000;
char answers[MAXQ];
Edge list[MAXM];
vector<size_t> last[MAXN];
std::bitset<MAXN> masks_r[MAXM / 2 + 10];
std::bitset<MAXN> masks_l[MAXM / 2 + 10];
void solve_layer(vector<Req>& requests, size_t l, size_t m, size_t r) {
bool has = false;
for (size_t i = 0; i != requests.size(); ++i)
has or_eq (requests[i].L <= m - 1 and requests[i].R >= m);
if (not has)
return;
for (size_t i = 0; i != r - m; ++i) {
masks_r[i] = std::bitset<MAXN>();
if (list[m + i].prev1 >= m and list[m + i].prev1 != std::numeric_limits<size_t>::max())
masks_r[i] |= masks_r[list[m + i].prev1 - m];
if (list[m + i].prev2 >= m and list[m + i].prev2 != std::numeric_limits<size_t>::max())
masks_r[i] |= masks_r[list[m + i].prev2 - m];
masks_r[i][list[m + i].v] = true;
masks_r[i][list[m + i].u] = true;
}
for (size_t z = 0; z != m - l; ++z) {
size_t i = (m - l) - 1 - z;
masks_l[i] = std::bitset<MAXN>();
if (list[l + i].next1 < m)
masks_l[i] |= masks_l[list[l + i].next1 - l];
if (list[l + i].next2 < m)
masks_l[i] |= masks_l[list[l + i].next2 - l];
masks_l[i][list[l + i].v] = true;
masks_l[i][list[l + i].u] = true;
}
for (size_t i = 0; i != requests.size();)
if (requests[i].L <= m - 1 and requests[i].R >= m) {
answers[requests[i].ID] = (masks_r[requests[i].R - m] & masks_l[requests[i].L - l]).any();
std::swap(requests[i], requests.back());
requests.pop_back();
} else {
++i;
}
}
void solve(vector<Req>& requests, size_t l, size_t r) {
if (l == r - 1) {
for (auto& req: requests)
answers[req.ID] = (req.S == list[l].v or req.S == list[l].u)
and (req.T == list[l].v or req.T == list[l].u);
return;
}
size_t m = l + (r - l) / 2;
// [l, m), [m, r).
solve_layer(requests, l, m, r);
vector<Req> right;
for (size_t i = 0; i != requests.size();)
if (requests[i].L >= m) {
right.push_back(requests[i]);
std::swap(requests[i], requests.back());
requests.pop_back();
} else {
++i;
}
requests.shrink_to_fit();
solve(requests, l, m);
solve(right, m, r);
}
int main() {
size_t n, m, q;
scanf("%d %d %d", &n, &m, &q);
assert(n <= MAXN);
assert(q <= MAXQ);
assert(m <= MAXM);
std::fill(answers, answers + q, 16);
for (size_t i = 0; i != m; ++i) {
scanf("%d %d", &list[i].v, &list[i].u);
--list[i].v, --list[i].u;
list[i].prev1 = list[i].prev2 = list[i].next1 = list[i].next2 = std::numeric_limits<size_t>::max();
if (not last[list[i].v].empty()) {
list[i].prev1 = last[list[i].v].back();
if (list[last[list[i].v].back()].v == list[i].v)
list[last[list[i].v].back()].next1 = i;
else {
list[last[list[i].v].back()].next2 = i;
}
}
if (not last[list[i].u].empty()) {
list[i].prev2 = last[list[i].u].back();
if (list[last[list[i].u].back()].v == list[i].u)
list[last[list[i].u].back()].next1 = i;
else {
list[last[list[i].u].back()].next2 = i;
}
}
last[list[i].v].push_back(i);
last[list[i].u].push_back(i);
}
vector<Req> requests;
for (size_t i = 0; i != q; ++i) {
Req req;
scanf("%d %d %d %d", &req.L, &req.R, &req.S, &req.T);
--req.L, --req.R, --req.S, --req.T;
req.ID = i;
auto it1 = std::lower_bound(last[req.S].begin(), last[req.S].end(), req.L);
auto it2 = std::upper_bound(last[req.T].begin(), last[req.T].end(), req.R);
if (it1 == last[req.S].end() or it2 == last[req.T].begin())
answers[i] = false;
else {
req.L = *it1;
req.R = *std::prev(it2);
if (req.L > req.R)
answers[i] = false;
else
requests.push_back(req);
}
}
solve(requests, 0, m);
for (size_t i = 0; i != q; ++i) {
printf("%s", (answers[i] ? "Yes\n" : "No\n"));
}
return 0;
}