結果
問題 | No.318 学学学学学 |
ユーザー |
|
提出日時 | 2024-06-11 15:36:57 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 214 ms / 2,000 ms |
コード長 | 2,453 bytes |
コンパイル時間 | 4,541 ms |
コンパイル使用メモリ | 269,100 KB |
最終ジャッジ日時 | 2025-02-21 21:06:48 |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h>// clang-format off#include <atcoder/all>using namespace std;using namespace atcoder;#define rep(i,n) for(int i=0;i<(n);i++)template<class T,class S>inline bool chmax(T &a,const S &b) {return (a<b? a=b,1:0);}template<class T,class S>inline bool chmin(T &a,const S &b) {return (a>b? a=b,1:0);}template<class T,class S>inline T floor(T a,S b) {if(b<0)a=-a,b=-b;return a>=0?a/b:(a+1)/b-1;}template<class T,class S>inline T ceil(T a,S b) {if(b<0)a=-a,b=-b;return a>0?(a-1)/b+1:a/b;}constexpr int dx[8]={1,0,-1,0,1,-1,1,-1},dy[8]={0,1,0,-1,1,-1,-1,1};using ll = long long;// clang-format on#ifdef LOCAL#include <util/debug_print.hpp>#else#define debug(...) static_cast<void>(0)#endif// 0始まりの座標へと圧縮するtemplate <typename T = long long> struct CC {bool initialized;vector<T> xs;CC() : initialized(false) {}void add(T x) { xs.push_back(x); }void init() {sort(xs.begin(), xs.end());xs.erase(unique(xs.begin(), xs.end()), xs.end());initialized = true;}int operator()(T x) {if (!initialized) init();return upper_bound(xs.begin(), xs.end(), x) - xs.begin() - 1;}T decode(int i) {if (!initialized) init();return xs[i];}int size() {if (!initialized) init();return xs.size();}};//// 区間更新 & 区間最大値取得//using S = ll;using F = ll;const S INF = 8e18;const F ID = 8e18;S op(S a, S b) {return max(a, b);}S e() {return -INF;}S mapping(F f, S x) {return (f == ID ? x : f);}F composition(F f, F g) {return (f == ID ? g : f);}F id() {return ID;}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin >> n;vector<ll> A(n);CC cc;rep(i, n) cin >> A[i], cc.add(A[i]);vector<ll> C(n);rep(i, n) C[i] = cc(A[i]);map<int, set<int>> mp;rep(i, n) mp[C[i]].insert(i);debug(mp);lazy_segtree<S, op, e, F, mapping, composition, id> seg(C);rep(x, cc.size()) {if (mp.count(x) == 0) continue;int l = 1001001001;int r = -1;for (auto i : mp[x]) {// if (seg.get(i) != x) continue;chmin(l, i), chmax(r, i);}if (r == -1) continue;seg.apply(l, r + 1, x);}rep(i, C.size()) cout << cc.decode(seg.get(i)) << ' ';cout << endl;return 0;}