提出 #41096155

---

ソースコード 拡げる

#include <atcoder/all>
using namespace atcoder;
#include <bits/stdc++.h>
#include <cassert>
using namespace std;
using ll = long long;
const double pi = 3.14159265359;
const ll INF = 1LL << 60;

template<class T> inline bool chmin(T& a, T b){ if (a > b){a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b){ if (a < b){a = b; return true;} return false;}

//using mint = modint998244353;
//using mint = modint1000000007;
//using mint = modint;  // mint::set_mod(p); later
//using mint = static_modint<1000000009>;

int op(int a, int b){ return min(a, b); }
int e() { return (int) 1e9; }

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

  int N, M;
  cin >> N >> M;
  vector<int> a(N);
  for (auto &&t : a) cin >> t;

  vector<vector<int>> ps(M+1);
  segtree<int, op, e> seg(N);

  for (int i = 0; i < N; i++){
    ps[a[i]].push_back(i);
    seg.set(i, a[i]);
  }

  // 各数字が一番最後に出現する位置
  set<int> st;
  for (int i = 1; i <= M; i++){
    int j = (int) ps[i].size() - 1;
    st.insert(ps[i][j]);
  }

  // Solve
  vector<int> b;
  int pos = 0;
  for (int i = 0; i < M; i++){
    while (seg.get(*st.begin()) > M){
      st.erase(st.begin());
    }
    int r = *st.begin();
    int x = seg.prod(pos, r + 1);
    b.push_back(x);
    for (int j : ps[x]){
      seg.set(j, e());
    }
    pos = *lower_bound(ps[x].begin(), ps[x].end(), pos) + 1;
  }

  for (int x : b) cout << x << " " ;
  cout << endl;
  return 0;
}

提出情報

ジャッジ結果