Как исправить TL?

Question

Задача:

Вагоны новой кольцевой железной дороги было предложено расписать N дизайнерам. Каждый дизайнер выбирал для своей раскраски полосу длиной li, начинающуюся от начала вагона и гарантированно помещающуюся на вагоне. Тем самым какие-то работы были полностью закрашены, а какие-то всё же были видны хотя бы частично.

Вам дана последовательность перекраски. После завершения работы каждого дизайнера выведите одно число — количество различных работ, элементы которых видны на момент завершения.

Формат ввода В первой строке дано количество дизайнеров 1 ≤ N ≤ 10^5 Во второй строке через пробел даны N целых чисел 1 ≤ l_i ≤ 10^9 – длины полос.

Формат вывода Выведите N чисел через пробел. i-е из этих чисел соответствует количеству различных работ, элементы которых видны после завершения работы i-го дизайнера.

Уже не знаю, что делать, чтобы быстрее работало

Пример 1

Ввод

3

1 3 2

Вывод

1

2

Пример 2

Ввод

2

5 5

Вывод

1

#include <iostream>
using namespace std;
int main() {
  unsigned long long int n, r = 0;
  cin >> n;
  unsigned long long int &s = n;
  int *l = new int[s];
  for (unsigned long long int i = 0; i < s; i++) {
    cin >> l[i];
    r++;
    if (l[i] >= l[i - 1]) {
      for (unsigned long long int t = 0; t < i; t++) {
        if (l[t] <= l[i] && l[t] != 0) {
          l[t] = 0;
          r--;
        }
      }
    }
    cout << r << endl;
  }
  delete [] l;
  return 0;
}

Answer 1

Линейный алгоритм:

 Берём стек.
 Цикл по дизайнерам:
     Для очередного значения L снимаем с вершины элементы, пока они <=L
     Вставляем L
     Выводим счётчик элементов стека


#include <iostream>
#include <stack>
using namespace std;
int main() {
    unsigned long long int n, l;
    cin >> n;
    stack<unsigned long long int> s;
    for (int i = 0; i < n; i++) {
        cin >> l;
        while (s.size() > 0 && s.top() <= l) s.pop();
        s.push(l);
        cout << s.size() << endl;
    }
    return 0;
}

БЛОГ НА HUSL

Как исправить TL?

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