Помогите решить задачу, пожалуйста. Вот условие:
На урок истории к Зинаиде Викторовне пришли n учеников. На дом было задано m тем, но у
учеников было мало времени для подготовки, поэтому i-й ученик выучил только темы с l_{i} по r_{i}
включительно.
В начале урока каждый ученик держит свою руку на уровне 0. Учительница хочет спросить
какие-то темы. Происходит это так:
• Учительница спрашивает тему k.
• Если ученик выучил тему k, то он поднимает руку на 1, а иначе опускает на 1.
Каждую тему Зинаида Викторовна может спросить не более 1 раза.
Найдите, какая максимальная разность между самой высокой и самой низкой рукой может быть
после опроса.
Обратите внимание, рука ученика может опускаться ниже 0.
Формат входных данных:
В первой строке содержатся два целых числа n и m (2\leq n\leq200 000, 1\leq m\leq10^{9}) — количество учеников и количество тем соответственно.
В каждой из следующих n строк содержатся по два целых числа l_{i} и r_{i} (1\leq l_{i} \leq r_{i} \leq m),
обозначающих границы отрезка тем, которые выучил i-й ученик.
Формат выходных данных:
Выведите одно число — максимальную разность между самой высокой и самой низкой рукой,
которая может быть в классе после опроса.
Есть код но почему-то он не работает:
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
#define ll long long
struct otr {
ll l, r;
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll n, m;
cin >> n >> m;
vector<otr> v(n);
for (ll i = 0; i < n; ++i) {
cin >> v[i].l >> v[i].r;
}
ll f = 0, last = 0;
for (ll i = 1; i < n; ++i) {
if (v[i].r < v[f].r) {
f = i;
}
else if (v[i].r == v[f].r && v[i].l < v[f].l) {
f = i;
}
if (v[i].l > v[last].l) {
last = i;
}
else if (v[i].l == v[last].l && v[i].r > v[last].r) {
last = i;
}
}
//cout << f << " " << last<<"\n";
vector<ll> ans(n);
for (ll i = 0; i < n; ++i) {
if (i == f) {
ans[i] = v[i].r - v[i].l + 1 - max((ll)0, v[i].r - v[last].l+1);
}
else if (i == last) {
ans[i] = v[i].r - v[i].l + 1 - max((ll)0, v[f].r - v[i].l+1);
}
else {
ll ans1, ans2;
ans1 = v[i].r - v[i].l + 1 - min(max((ll)0, v[i].r - v[last].l+1), v[last].r - v[last].l + 1);
ans2 = v[i].r - v[i].l + 1 - min(max((ll)0, v[f].r - v[i].l+1), v[f].r - v[f].l + 1);
ans[i] = max(ans1, ans2);
}
}
ll cnt = ans[0];
for (ll i = 0; i < n; ++i) {
cnt = max(cnt, ans[i]);
}
cout << cnt*2;
return 0;
}
Суть следующая. Разность в высоте рук двух учеников определяется темами, которые знает ровно 1 из них. Тогда зафиксируем какой-то отрезок [l_{i};r_{i}]. Найдём максимальную разность, которая может получится между этим учеником и каким-нибудь другим (пусть его номер j). У нас может быть 4 вида пересечений. Первый это когда один из отрезков покрывает другой полностью. В этом случае 0. Второй это когда l_{j}\leq l_{i}\leq r_{j}\leq r_{i}. В таком случае эта разность равна 2\cdot((r_{i}-l_{i}+1)-(r_{j}-l_{i}+1)). Тогда она зависит от r_{j}, значит для максимальной разности r_{j}=r_{min}. Третий случай это когда l_{i}\leq l_{j}\leq r_{i}\leq r_{j}. В таком случае эта разность равна 2\cdot((r_{i}-l_{i}+1)-(r_{i}-l_{j}+1)). Тогда она зависит от l_{j}, значит для максимальной разности l_{j}=l_{max}. И четвёртый это когда у нас отрезки не пересекаются. В этом случае максимальная разность равна длине отрезка [l_{i};r_{i}] умноженной на два. Исходя из этих случаев, можно понять, что для каждого отрезка можно разобрать эти случаи и взять в качестве отрезка [l_{j};r_{j}] отрезки [l_{f};r_{min}] и [l_{max};r_{last}] (l_{f} и r_{last} по идее могут быть любыми, главное чтобы отрезки были в нашем списке). И остаётся взять максимальную из этих разностей.
Идея вроде рабочая, правда код почему-то работает не на всех тестах (на 5 из 20). Пожалуйста, помогите найти ошибку. Ну или хотя бы придумайте каких-нибудь тестов.