Submission #869576

#	Time	Username	Problem	Language	Result	Execution time	Memory
869576		LucaLucaM	Stone Arranging 2 (JOI23_ho_t1)	C++17	60 / 100	2102 ms	10024 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cstring>
#include <functional>
#include <set>
#include <stack>
#warning That's the baby, that's not my baby

typedef long long ll;

bool inside (std::tuple<int, int, int> a, std::tuple<int, int, int> b) {
  int x1 = std::get<0>(a), y1 = std::get<1>(a);
  int x2 = std::get<0>(b), y2 = std::get<1>(b);
  return (x1 <= x2 && y2 <= y1);
}

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);

  int n;
  std::cin >> n;
  int a[n];
  std::stack<int> st;
  std::set<int> inStack;
  std::vector<std::tuple<int, int, int>> updates;

  for (int i = 0; i < n; i++) {
    std::cin >> a[i];
    if (inStack.count(a[i])) {
      while (a[st.top()] != a[i]) {
        inStack.erase(a[st.top()]);
        st.pop();
      }
      std::tuple<int, int, int> cur = {st.top(), i, a[i]};
      if (!updates.empty() && inside(updates.back(), cur)) {
        updates.pop_back();
      }
      updates.push_back(cur);
      st.pop();
      st.push(i);
    } else {
      inStack.insert(a[i]);
      st.push(i);
    }
  }

  for (const auto &[l, r, v] : updates) {
    for (int i = l; i <= r; i++) {
      a[i] = v;
    }
  }

  for (int i = 0; i < n; i++) {
    std::cout << a[i] << '\n';
  }

  return 0;
}

Compilation message (stderr)

Main.cpp:9:2: warning: #warning That's the baby, that's not my baby [-Wcpp]
    9 | #warning That's the baby, that's not my baby
      |  ^~~~~~~

• Subtask 1: 25 / 25
• Subtask 2: 35 / 35
• Subtask 3: 0 / 40