Submission #978192

#	Time	Username	Problem	Language	Result	Execution time	Memory
978192		asdfgrace	Stone Arranging 2 (JOI23_ho_t1)	C++17	100 / 100	58 ms	16200 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define dbg(x) x
#define prt(x) dbg(cerr << x)
#define pv(x) dbg(cerr << #x << " = " << x << '\n')
#define pv2(x) dbg(cerr << #x << " = " << x.first << ',' << x.second << '\n')
#define parr(x) dbg(prt(#x << " = { "); for (auto y : x) prt(y << ' '); prt("}\n");)
#define parr2(x) dbg(prt(#x << " = { "); for (auto [y, z] : x) prt(y << ',' << z << "  "); prt("}\n");)
#define parr2d(x) dbg(prt(#x << ":\n"); for (auto arr : x) {parr(arr);} prt('\n'));
#define parr2d2(x) dbg(prt(#x << ":\n"); for (auto arr : x) {parr2(arr);} prt('\n'));

/*
if said elem has a previous occurrence
delete ranges from the array and decrease the counts
until you get to the previous occurrence
and extend the right bound from there to i
else
you just add a range of length 1 ending at i and increase the cnt by 1
*/

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  vector<int> ord(n);
  iota(ord.begin(), ord.end(), 0);
  sort(ord.begin(), ord.end(), [&] (int x, int y) {
    return a[x] < a[y];
  });
  vector<int> b(n), val(1, a[ord[0]]);
  vector<vector<int>> at(n);
  int cur = 0;
  for (int i = 0; i < n; i++) {
    if (i > 0 && a[ord[i]] > a[ord[i - 1]]) {
      cur++;
      val.push_back(a[ord[i]]);
    }
    b[ord[i]] = cur;
  }
  vector<int> cnt(n, 0);
  vector<array<int, 3>> r;
  for (int i = 0; i < n; i++) {
    if (cnt[b[i]]) {
      while (r.size() && r[r.size() - 1][0] != b[i]) {
        cnt[r[r.size() - 1][0]]--;
        r.pop_back();
      }
      assert(r.size() && r[r.size() - 1][0] == b[i]);
      r[r.size() - 1][2] = i;
    } else {
      cnt[b[i]]++;
      r.push_back({b[i], i, i});
    }
  }
  for (auto [k, lb, rb] : r) {
    for (int i = lb; i <= rb; i++) {
      cout << val[k] << '\n';
    }
  }
}

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