Nearest Smaller Values

Link: 1645

Fonte: CSES problemset

Categoria

minqueue

Sketch

Per risolvere il problema ci basta usare una minqueue, modificando opportunamente la funzione add affinché ritorni il valore in fondo prima di aggiungerne uno nuovo. Nell'implementazione viene usata una struct, se non vi è chiaro qualcosa potete chiedere a noi o provare a controllare su internet, ad esempio https://www.w3schools.com/cpp/cpp_structs.asp.

Soluzione

#include <bits/stdc++.h>
 
using namespace std;
 
struct MinQueue {
  deque<array<int, 2>> q;

  void add(int x, int i) {
    while (!q.empty() && q.back()[0] >= x) {
      q.pop_back();
    }
    int r = q.back()[1];
    q.push_back({x, i});
    return r;
  }
};
 
int main() {
  int N; cin >> N;

  vector<int> X(N);
  for (int i = 0; i < N; i++) {
    cin >> X[i];
  }

  MinQueue Q;
  Q.push({0, 0});
  for (int i = 0; i < N; i++) {
    cout << Q.add(X[i], i + 1) << ' ';
  }
  cout << '\n';
  return 0;
}