Submission #869590

#	Time	Username	Problem	Language	Result	Execution time	Memory
869590		LucaLucaM	Stone Arranging 2 (JOI23_ho_t1)	C++17	0 / 100	1 ms	604 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;

struct Update {
  int l, r, v;
};

bool inside (const Update &a, const Update &b) {
  return (a.l <= b.l && b.r <= a.r);
}

bool partial (Update a, Update b) {
  if (a.l > b.l) {
    std::swap(a, b);
  }
  if (a.r < b.l) {
    return false;
  }
  return (b.l <= a.r);
}

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

  int n;
  std::cin >> n;
  int a[n];
  std::stack<int> st;
  std::set<int> inStack;
  std::vector<Update> 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();
      }
      Update cur = {st.top() + 1, i - 1, a[i]};

      while (!updates.empty() && inside(updates.back(), cur)) {
        updates.pop_back();
      }
      if (!updates.empty()) {
        assert(!partial(updates.back(), cur));
      }
      updates.push_back(cur);
      st.pop();
      st.push(i);
    } else {
      inStack.insert(a[i]);
      st.push(i);
    }
  }

  int sumLen = 0;
  for (const auto &[l, r, v] : updates) {
    sumLen += r - l + 1;
//    std::cout << l << ' ' << r << ' ' << v << '\n';
    assert(sumLen <= 2 * n);
  }

  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: 0 / 25
• Subtask 2: 0 / 35
• Subtask 3: 0 / 40