結果
問題 | No.318 学学学学学 |
ユーザー |
|
提出日時 | 2020-02-07 18:59:44 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 223 ms / 2,000 ms |
コード長 | 3,921 bytes |
コンパイル時間 | 1,962 ms |
コンパイル使用メモリ | 134,932 KB |
実行使用メモリ | 17,024 KB |
最終ジャッジ日時 | 2024-09-25 07:25:20 |
合計ジャッジ時間 | 7,184 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <cstdio>#include <iostream>#include <string>#include <sstream>#include <stack>#include <algorithm>#include <cmath>#include <queue>#include <map>#include <set>#include <cstdlib>#include <bitset>#include <tuple>#include <assert.h>#include <deque>#include <bitset>#include <iomanip>#include <limits>#include <chrono>#include <random>#include <array>#include <unordered_map>#include <functional>#include <complex>template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }const long long MAX = 5100000;const long long INF = 1LL << 60;const long long mod = 1000000007LL;//const long long mod = 998244353LL;using namespace std;typedef unsigned long long ull;typedef long long ll;template <typename T, typename E>struct lazySegTree {using F = function<T(T, T)>;using G = function<T(T, E)>;using H = function<E(E, E)>;using P = function<E(E, int)>;F f; G g; H h; P p; T d1; E d0;int n;vector<T> dat;vector<E> lazy;lazySegTree() {}lazySegTree(int n_, F f_, G g_, H h_,T d1_, E d0_, P p_ = [](E a, int b) {return a; }): f(f_), g(g_), h(h_), p(p_), d1(d1_), d0(d0_){n = 1; while (n < n_) n *= 2;dat.assign(n * 2 - 1, d1);lazy.assign(n * 2 - 1, d0);}void build(vector<T> v) {for (ll i = 0; i < v.size(); i++) dat[i + n - 1] = v[i];for (int i = n - 2; i >= 0; --i) dat[i] = f(dat[i * 2 + 1], dat[i * 2 + 2]);}// 区間の幅がlenの節点kについて遅延評価inline void eval(int len, int k) {if (lazy[k] == d0) return;if (k * 2 + 1 < n * 2 - 1) {lazy[2 * k + 1] = h(lazy[k * 2 + 1], lazy[k]);lazy[2 * k + 2] = h(lazy[k * 2 + 2], lazy[k]);}dat[k] = g(dat[k], p(lazy[k], len));lazy[k] = d0;}// [a, b)T update(int a, int b, E x, int k, int l, int r) {eval(r - l, k);if (b <= l || r <= a) return dat[k];if (a <= l && r <= b) {lazy[k] = h(lazy[k], x);return g(dat[k], p(lazy[k], r - l));}return dat[k] = f(update(a, b, x, 2 * k + 1, l, (l + r) / 2),update(a, b, x, 2 * k + 2, (l + r) / 2, r));}T update(int a, int b, E x) { return update(a, b, x, 0, 0, n); }// [a, b)T query(int a, int b, int k, int l, int r) {eval(r - l, k);if (a <= l && r <= b) return dat[k];bool left = !((l + r) / 2 <= a || b <= l), right = !(r <= 1 || b <= (l + r) / 2);if (left && right) return f(query(a, b, 2 * k + 1, l, (l + r) / 2), query(a, b, 2 * k + 2, (l + r) / 2, r));if (left) return query(a, b, 2 * k + 1, l, (l + r) / 2);return query(a, b, 2 * k + 2, (l + r) / 2, r);}T query(int a, int b) { return query(a, b, 0, 0, n); }};/*** 区間更新区間max d1=d0=INT_MAX f=max(a,b) g=h=(b==INT_MAX?a:b)\n* 区間加算区間和 d1=d0=0 f=g=h=a+b p=a*b\n* 区間加算区間min d1=d0=0 f=min(a,b) g=h=a+b\n* 区間更新区間和 d1=d0=0 f=a+b g=h=(b==0?a:b) p=a*b\n* 区間xor区間和 d1=d0=0 f=a+b g=(b>=1?b-a:a) h=a^b p=a*b*/ll f(ll a, ll b) {return min(a, b);}ll g(ll a, ll b) {if (b == INF) return a;else return b;}int main(){/*cin.tie(nullptr);ios::sync_with_stdio(false);*/ll n; scanf("%lld", &n);vector<ll> a(n); for (ll i = 0; i < n; i++) scanf("%lld", &a[i]);vector<ll> left(n, INF), right(n, -1), cnv(n);map<ll, int> mp;{int id = 0;for (ll i = 0; i < n; i++) mp[a[i]] = 0;for (auto itr = mp.begin(); itr != mp.end(); itr++) itr->second = id++;for (auto p : mp) cnv[p.second] = p.first;for (ll i = 0; i < n; i++) chmin(left[mp[a[i]]], i), chmax(right[mp[a[i]]], i);}lazySegTree<ll, ll> lsg(n + 1, f, g, g, INF, INF);for (ll i = 0; i < n; i++) {if (left[i] == INF) continue;lsg.update(left[i], right[i] + 1, i);}for (ll i = 0; i < n; i++) {printf("%lld", cnv[lsg.query(i, i + 1)]);if (i == n - 1) puts("");else printf(" ");}return 0;}