結果

問題 No.318 学学学学学
コンテスト
ユーザー peroon
提出日時 2019-11-21 21:56:40
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 546 ms / 2,000 ms
コード長 5,839 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,029 ms
コンパイル使用メモリ 187,308 KB
実行使用メモリ 22,912 KB
最終ジャッジ日時 2024-10-11 02:08:36
合計ジャッジ時間 9,919 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using VI = vector<ll>;
using VV = vector<VI>;
using VS = vector<string>;

// tourist set
template <typename A, typename B>
string to_string(pair<A, B> p);

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);

string to_string(const string& s) {
  return '"' + s + '"';
}

string to_string(const char* s) {
  return to_string((string) s);
}

string to_string(bool b) {
  return (b ? "true" : "false");
}

string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}

template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}

template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}

void debug_out() { cerr << '\n'; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
// tourist set end

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i,b) FOR(i, 0, b)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<'\n'
#define p2(s, t) cout << (s) << " " << (t) << '\n'
#define br() p("")
#define pn(s) cout << (#s) << " " << (s) << '\n'
#define p_yes() p("YES")
#define p_no() p("NO")
#define SZ(x) ((int)(x).size())
#define SORT(A) sort(ALL(A))
#define RSORT(A) sort(ALL(A), greater<ll>())

void no(){p_no(); exit(0);}
void yes(){p_yes(); exit(0);}

const ll mod = 1e9 + 7;
const ll inf = 1e18;
const double PI = acos(-1);

struct RBST {
	struct node {
		ll val, size;
		node *lch, *rch;
		ll mx;
		ll lazy;
		node(ll val) : val(val), mx(val), size(1), lch(0), rch(0), lazy(-1) {}
	};
	node *root;
	RBST(ll n) {
		root = build(0, n);
	}
	node *build(ll l, ll r) {
		if (r - l == 1) return new node(0);
		return merge(build(l, (l + r) / 2), build((l + r) / 2, r));
	}

	unsigned xor32() {
		static unsigned z = time(NULL);
		z ^= z << 13; z ^= z >> 17; z ^= z << 5;
		return z;
	}
	ll size(node *x) {
		return x ? x->size : 0;
	}
	ll mx(node *x) {
		return x ? x->mx : -inf;
	}
	node *push(node *x) {
		x->size = 1 + size(x->lch) + size(x->rch);
		if (x->lazy != -1) {
			x->val = x->lazy;
			if (x->lch) x->lch->lazy = x->lazy;
			if (x->rch) x->rch->lazy = x->lazy;
			x->lazy = -1;
		}
		x->mx = max({ x->val, mx(x->lch), mx(x->rch) });
		return x;
	}
	node *merge(node *x, node *y) {
		if (!x) return y;
		if (!y) return x;
		if (xor32() % (size(x) + size(y)) < size(x)) {
			x = push(x);
			x->rch = merge(x->rch, y);
			return push(x);
		} else {
			y = push(y);
			y->lch = merge(x, y->lch);
			return push(y);
		}
	}
	pair<node *, node *> split(node *x, ll k) {
		if (!x) return{ 0, 0 };
		x = push(x);
		if (size(x->lch) >= k) {
			auto p = split(x->lch, k);
			x->lch = p.second;
			return{ p.first, push(x) };
		} else {
			auto p = split(x->rch, k - size(x->lch) - 1);
			x->rch = p.first;
			return{ push(x), p.second };
		}
	}
	node *insert(node *x, ll k, ll v) {
		auto p = split(x, k);
		node *n = new node(v);
		return merge(p.first, merge(n, p.second));
	}
	node *erase(node *x, ll k) {
		auto p = split(x, k);
		return merge(p.first, split(p.second, 1).second);
	}
	void push_back(ll v) {
		root = merge(root, new node(v));
	}
	ll lower_bound(node *x, ll v) {
		if (!x) return 0;
		if (v < x->val) return lower_bound(x->lch, v);
		return lower_bound(x->rch, v) + size(x->lch) + 1;
	}
	node *at(node *x, ll k) {
		if (size(x->lch) == k) return x;
		if (size(x->lch) > k) return at(x->lch, k);
		return at(x->rch, k - size(x->lch) - 1);
	}

	void update(ll a, ll b, ll v) {
		auto x = split(root, b);
		auto y = split(x.first, a);
		y.second->lazy = v;
		root = merge(merge(y.first, y.second), x.second);
	}

	ll query(ll a, ll b) {
		auto x = split(root, b);
		auto y = split(x.first, a);
		ll ret = mx(y.second);
		root = merge(merge(y.first, y.second), x.second);
		return ret;
	}
};

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

    // input
    ll N; 
    cin >> N;

    VI A(N);
    rep(i, N){
      cin >> A.at(i);
    }

    map<ll, ll> first, last;
    rep(i, N){
      ll a = A[i];
      last[a] = i;
    }
    for(int i=N-1; i>=0; i--){
      ll a = A[i];
      first[a] = i;
    }

    auto seg = RBST(N);
    for(auto kv : first){
      ll v = kv.first;
      ll l = first[v];
      ll r = last[v];
      seg.update(l, r+1, v);
    }

    rep(i, N){
      if(i) cout << ' ';
      cout << seg.query(i, i+1);
    }
    cout << endl;
    
    return 0;
}
0