Задача "Модник"

Question

Знаю, что уже есть, не хватает репутации комментировать и отвечать.

Всего в одном месяце 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;
}

Answer 1

Задачу можно решить несколькими способами. Скан лайн(сканирующая прямая) один из наиболее оптимальных(ДО не будет работать из-за большого кол-во дней в месяце). Для того чтобы решить эту задачу с помощью скан лайна нужно обработать каждое событие(начало и конец ивента) во временном порядке. Все суммы мы храним в сете, чтобы оперативно добавлять туда элемент и извлекать. Обрабатывая день к суме мы прибавляем длительность между событиями и минимальную цену этого события.

int n, m;
cin >> n >> m;
deque <pair<int,int>> dates;
for (size_t i = 0; i < m; i++){
    int l, r, x;
    cin >> l >> r >> x;
    dates.push_back({l,x});
    dates.push_back({r+1,-x});
}
sort(dates.begin(), dates.end());
multiset <int, greater<int>> cost;
long long sum = 0;
cost.insert(0);
int pday = dates.front().first;
while (dates.size()){
    pair<int,int> s = dates.front();
    sum += (s.first-pday)*(*cost.begin());
    if(s.second < 0){
        cost.erase(cost.find(-s.second));
    } else {
        cost.insert(s.second);
    }
    pday = s.first;
    dates.pop_front();
}
cout << sum << endl;

БЛОГ НА HUSL

Задача "Модник"

Ответы (1 шт):