結果

問題 No.318 学学学学学
コンテスト
ユーザー _yes
提出日時 2025-11-04 01:25:48
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 200 ms / 2,000 ms
コード長 3,935 bytes
コンパイル時間 3,375 ms
コンパイル使用メモリ 286,612 KB
実行使用メモリ 18,560 KB
最終ジャッジ日時 2025-11-04 01:25:56
合計ジャッジ時間 7,751 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i< (n); ++i)
#define repi(i, a, b) for (int i = (a); i < (b); ++i)
#define all(x) (x).begin(), (x).end()
#define fore(i, a) for(auto &i:a)
using ll = long long;
using int64 = long long;
#define DEBUG(x) cerr << #x << ": "; for (auto _ : x) cerr << _ << " "; cerr << endl;
const int64 infll = (1LL << 62) - 1;
const int inf = (1 << 30) - 1;

struct IoSetup {
	IoSetup() {
		cin.tie(nullptr);
		ios::sync_with_stdio(false);
		cout << fixed << setprecision(10);
		cerr << fixed << setprecision(10);
	}
} iosetup;

template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
	os << p.first << " " << p.second;
	return os;
}

template <typename T1, typename T2>
istream& operator>>(istream& is, pair<T1, T2>& p) {
	is >> p.first >> p.second;
	return is;
}

template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
	for (int i = 0; i < (int)v.size(); i++) {
		os << v[i] << (i + 1 != v.size() ? " " : "");
	}
	return os;
}

template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
	for (T& in : v) is >> in;
	return is;
}

template <typename T1, typename T2>
inline bool chmax(T1& a, T2 b) {
	return a < b && (a = b, true);
}

template <typename T1, typename T2>
inline bool chmin(T1& a, T2 b) {
	return a > b && (a = b, true);
}

template <typename T = int64>
vector<T> make_v(size_t a) {
	return vector<T>(a);
}

template <typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
	return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}

template <typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type fill_v(T& t, const V& v) {
	t = v;
}

template <typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type fill_v(T& t, const V& v) {
	for (auto& e : t) fill_v(e, v);
}

template <typename F>
struct FixPoint : F {
	explicit FixPoint(F&& f) : F(std::forward<F>(f)) {}

	template <typename... Args>
		decltype(auto) operator()(Args&&... args) const {
			return F::operator()(*this, std::forward<Args>(args)...);
		}
};

template <typename F>
inline decltype(auto) MFP(F&& f) {
	return FixPoint<F>{std::forward<F>(f)};
}
struct Act {
  using F = ll;
  static constexpr F composition(const F &f, const F &g) {return g;}
  static constexpr F id() {return -1;}
};
template <typename Act>
struct DualSegmentTree {
  using F = typename Act::F;

 private:
  int sz, height;
  vector<F> lazy;
  Act m;

  inline void propagate(int k) {
    if (lazy[k] != m.id()) {
      lazy[2 * k + 0] = m.composition(lazy[2 * k + 0], lazy[k]);
      lazy[2 * k + 1] = m.composition(lazy[2 * k + 1], lazy[k]);
      lazy[k] = m.id();
    }
  }

  inline void thrust(int k) {
    for (int i = height; i > 0; i--) propagate(k >> i);
  }

 public:
  DualSegmentTree(Act m, int n) : m(m) {
    sz = 1;
    height = 0;
    while (sz < n) sz <<= 1, height++;
    lazy.assign(2 * sz, m.id());
  }

  F get(int k) {
    thrust(k += sz);
    return lazy[k];
  }

  F operator[](int k) { return get(k); }

  void apply(int a, int b, const F& f) {
    thrust(a += sz);
    thrust(b += sz - 1);
    for (int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {
      if (l & 1) lazy[l] = m.composition(lazy[l], f), ++l;
      if (r & 1) --r, lazy[r] = m.composition(lazy[r], f);
    }
  }
};
int main(){
	ll n; cin >> n;
	vector<ll> a(n);rep(i, n)cin >> a[i];
	Act m;
	DualSegmentTree D(m, n);
	rep(i, n){
		D.apply(i,i+1,a[i]);
	}
	map<ll,ll> L, R;
	rep(i, n){
		if(L.count(a[i]))continue;
		L[a[i]] = i;
	}
	rep(ii, n){
		ll i = n-1-ii;
		if(R.count(a[i]))continue;
		R[a[i]] = i;
	}
	for(auto[key, l]:L){
		ll r = R[key];
		D.apply(l, r+1, key);
	}
	rep(i, n){
		cout << D[i] << " ";
	}
	cout << "\n";


	
	
}
0