結果
問題 | No.318 学学学学学 |
ユーザー |
|
提出日時 | 2021-02-01 02:47:35 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 162 ms / 2,000 ms |
コード長 | 3,953 bytes |
コンパイル時間 | 2,437 ms |
コンパイル使用メモリ | 142,304 KB |
最終ジャッジ日時 | 2025-01-18 10:33:48 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <iostream>#include <vector>#include <algorithm>#include <cmath>#include <queue>#include <string>#include <map>#include <set>#include <stack>#include <tuple>#include <deque>#include <array>#include <numeric>#include <bitset>#include <iomanip>#include <cassert>#include <chrono>#include <random>#include <limits>#include <iterator>#include <functional>#include <sstream>#include <fstream>#include <complex>#include <cstring>#include <unordered_map>#include <unordered_set>using namespace std;using ll = long long;constexpr int INF = 1001001001;constexpr int mod = 1000000007;// constexpr int mod = 998244353;template<class T>inline bool chmax(T& x, T y){if(x < y){x = y;return true;}return false;}template<class T>inline bool chmin(T& x, T y){if(x > y){x = y;return true;}return false;}template<typename Monoid, typename OperatorMonoid = Monoid>struct LazySegmentTree{using F = function<Monoid(Monoid, Monoid)>;using G = function<Monoid(Monoid, OperatorMonoid)>;using H = function<OperatorMonoid(OperatorMonoid, OperatorMonoid)>;int sz;vector<Monoid> data;vector<OperatorMonoid> lazy;const F f;const G g;const H h;const Monoid M1; // モノイドの単位元const OperatorMonoid OM0; // 作用素モノイドの単位元LazySegmentTree(int n, const F f, const G g, const H h, const Monoid &M1, const OperatorMonoid OM0): f(f), g(g), h(h), M1(M1), OM0(OM0){sz = 1;while(sz < n) sz <<= 1;data.assign(sz << 1, M1);lazy.assign(sz << 1, OM0);}void set(int k, const Monoid &x){data[k + sz] = x;}void build(){for(int k = sz - 1; k > 0; --k){data[k] = f(data[k << 1], data[k << 1 | 1]);}}void propagate(int k){if(lazy[k] != OM0){if(k < sz){lazy[k << 1] = h(lazy[k << 1], lazy[k]);lazy[k << 1 | 1] = h(lazy[k << 1 | 1], lazy[k]);}data[k] = g(data[k], lazy[k]);lazy[k] = OM0;}}Monoid update(int a, int b, const OperatorMonoid &x, int k = 1, int l = 0, int r = -1){if(r == -1) r = sz;propagate(k);if(r <= a || b <= l) return data[k];else if(a <= l && r <= b){lazy[k] = h(lazy[k], x);propagate(k);return data[k];}else{return data[k] = f(update(a, b, x, k << 1, l, (l + r) >> 1),update(a, b, x, k << 1 | 1, (l + r) >> 1, r));}}Monoid query(int a, int b, int k = 1, int l = 0, int r = -1){if(r == -1) r = sz;propagate(k);if(r <= a || b <= l) return M1;else if(a <= l && r <= b) return data[k];else{return f(query(a, b, k << 1, l, (l + r) >> 1),query(a, b, k << 1 | 1, (l + r) >> 1, r));}}Monoid operator[](const int &k){return query(k, k + 1);}};int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int N;cin >> N;vector<int> a(N), xs(N);for(int i = 0; i < N; ++i){cin >> a[i];xs[i] = a[i];}sort(xs.begin(), xs.end());xs.erase(unique(xs.begin(), xs.end()), xs.end());int K = xs.size();vector<int> l(K, N), r(K);for(int i = 0; i < N; ++i){int j = lower_bound(xs.begin(), xs.end(), a[i]) - xs.begin();chmin(l[j], i); chmax(r[j], i + 1);}auto op = [](int a, int b){return max(a, b);};LazySegmentTree<int, int> seg(N, op, op, op, 0, 0);for(int i = 0; i < K; ++i){seg.update(l[i], r[i], xs[i]);}for(int i = 0; i < N; ++i){cout << seg[i] << (i == N - 1 ? '\n' : ' ');}return 0;}