Знаю, что уже есть, не хватает репутации комментировать и отвечать.
Всего в одном месяце n дней. Вы знаете, что в этом месяце будет проходить m фэшн-эвентов. i-й фэшн-эвент будет проходить со дня li по день ri включительно. Во все дни i-го фэшн-эвента стоимость вашего наряда должна быть хотя бы xi. Конечно же нельзя носить одно и то же, поэтому каждый день, когда проходит хотя бы один фэшн-эвент, вы покупаете новый наряд. Заметьте, что в один день может быть несколько эвентов, но для них надо купить только один наряд. Сообщите минимальное суммарное количество денег, которое потребуется, чтобы удовлетворить условия всех фэшн-эвентов.
Формат ввода В первой строке вводится два числа n и m (1 ≤ n ≤ 109, 1 ≤ m ≤ 105). Следующие m строк описывают фэшн-эвенты. В i-й строке записаны 3 числа li, ri и xi (1 ≤ li ≤ ri ≤ n, 1 ≤ xi ≤ 109) — даты фэшн-эвента и минимальная стоимость наряда.
Формат вывода Выведите минимальное суммарное количество денег, необходимое для удовлетворения условий всех фэшн-эвентов.
Пример 1
Ввод Вывод
10 3 63
1 5 5
6 10 6
3 7 7
Пример 2
Ввод Вывод
3 4 9
1 2 2
2 3 3
2 2 1
2 2 4
Есть решение, похожее на https://ru.stackoverflow.com/questions/1396284/Задача-модник-на-c/1397005, оно работает, но долго.(Человек забыл инициализировать вектор, ответьте ему, пожалуйста, если не сложно). И собственно вопрос: как сделать код быстрее?
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio();
cin.tie(0);
cout.tie(0);
long long n, m, r, l, x;
cin >> n >> m;
vector<long long> mass(n + 1, 0);
for (int i = 0; i < m; ++i) {
cin >> r >> l >> x;
for (long long j = r; j <= l; ++j) {
mass[j] = max(mass[j], x);
}
}
long long ans = 0;
for (int i = 1; i < n + 1; ++i) {
ans += mass[i];
}
cout << ans;
}