Submission #776933

#	Time	Username	Problem	Language	Result	Execution time	Memory
776933		ind1v	Stone Arranging 2 (JOI23_ho_t1)	C++11	100 / 100	173 ms	35656 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int N = 200005;

int n;
int a[N];
vector<int> v;
set<int> idx[N];
set<int> indices;
int l[N], ans[N];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  copy(a + 1, a + n + 1, back_inserter(v));
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), v.end());
  for (int i = 1; i <= n; i++) {
    a[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin();
    if (!idx[a[i]].empty()) {
      int lst = *idx[a[i]].rbegin();
      vector<int> removals;
      for (auto it = indices.upper_bound(lst); it != indices.end(); it++) {
        idx[a[*it]].erase(*it);
        removals.emplace_back(*it);
      }
      for (auto &x : removals) {
        indices.erase(x);
      }
      l[i] = lst;
    } else {
      l[i] = i;
    }
    idx[a[i]].insert(i);
    indices.insert(i);
  }
  for (int i = n, j = n; i >= 1; i--) {
    while (j >= l[i]) {
      ans[j--] = a[i];
    }
  }
  for (int i = 1; i <= n; i++) {
    cout << v[ans[i]] << '\n';
  }
  return 0;
}

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