結果
問題 | No.318 学学学学学 |
ユーザー |
![]() |
提出日時 | 2018-04-21 10:44:36 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 906 ms / 2,000 ms |
コード長 | 3,416 bytes |
コンパイル時間 | 1,669 ms |
コンパイル使用メモリ | 181,828 KB |
実行使用メモリ | 15,744 KB |
最終ジャッジ日時 | 2024-06-22 18:32:42 |
合計ジャッジ時間 | 10,207 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include<bits/stdc++.h>using namespace std;using ll = long long;template<class T> using vt = vector<T>;template<class T> using vvt = vector<vt<T>>;template<class T> using ttt = tuple<T,T>;using tii = tuple<int,int>;using vi = vector<int>;#define rep(i,n) for(int i=0;i<(int)(n);i++)#define pb push_back#define mt make_tuple#define ALL(a) (a).begin(),(a).end()#define FST first#define SEC second#define DEB cerr<<"!"<<endl#define SHOW(a,b) cerr<<(a)<<" "<<(b)<<endl#define DIV int(1e9+7)const int INF = (INT_MAX/2);const ll LLINF = (LLONG_MAX/2);const double eps = 1e-8;//const double PI = M_PI;inline ll pow(ll x,ll n,ll m){ll r=1;while(n>0){if((n&1)==1)r=r*x%m;x=x*x%m;n>>=1;}return r%m;}inline ll lcm(ll d1, ll d2){return d1 / __gcd(d1, d2) * d2;}/*願はくは花の下にて春死なんそのきさらぎの望月のころ(西行 1118-1190)--This is old Japanese poem expressing the desire to die under tree on the full moon night.(written by Saigyo)In my research, there is possibility that the tree may be seg-tree.*//*Coding Space*/// This Segtree written by qcw_pro(my team mate).template <class M, class O> // M: monoid, O: operator monoidstruct SegTree {using MM = function <M(M, M)>;using MO = function <M(M, O)>;using OO = function <O(O, O)>;using OI = function <O(O, int)>;const int n, h; // n: array size, h: height of treeconst M m_id; // identity element of monoidconst O o_id; // identity element of operator monoidMM mm; MO mo; OO oo; OI oi;vector<M> m; // monoid arrayvector<O> o; // operator monoid arraySegTree(int n, M m_id, O o_id, MM mm, MO mo, OO oo,OI oi = [](const O& a, int b) { return a; }):n(n), h(sizeof(int)*CHAR_BIT - __builtin_clz(n)),m_id(m_id), o_id(o_id), mm(mm), mo(mo), oo(oo), oi(oi),m(n * 2, m_id), o(n * 2, o_id) {}inline void apply(int i, const O& v, int k) {m[i] = mo(m[i], oi(v, k));if(i < n) o[i] = oo(o[i], v);}inline void build(int i) {while(i >>= 1)if(o[i] == o_id)m[i] = mm(m[i * 2], m[i * 2 + 1]);}inline void push(int i) {int s{ i >> h ? h : h - 1 };for(int k{ 1 << (s - 1) }; s > 0; --s, k >>= 1) {int p{ i >> s };if(o[p] == o_id) continue;apply(p * 2, o[p], k);apply(p * 2 + 1, o[p], k);o[p] = o_id;}}void modify(int l, int r, const O& v) {l += n, r += n;push(l), push(r - 1);int ll{ l }, rr{ r };for(int k{ 1 }; l < r; l >>= 1, r >>= 1, k <<= 1) {if(l & 1) apply(l++, v, k);if(r & 1) apply(r - 1, v, k);}build(ll), build(rr - 1);}M query(int l, int r) { // [l,r)l += n, r += n;push(l), push(r - 1);M a{ m_id }, b{ m_id };for(; l < r; l >>= 1, r >>= 1) {if(l & 1) a = mm(a, m[l++]);if(r & 1) b = mm(m[r - 1], b);}return mm(a, b);}};//SegTree<input type, operator type> (size, M_I, O_I, MM, MO, OO)int F (int a, int b){return max(a, b);};SegTree<int,int> st(100005, 0, 0, F, F,F);int main(){int n; cin >> n;map<int,vector<int>> in;rep(i,n){int ii; cin >> ii;in[ii].pb(i);}for(auto&& i:in){int a; int b;if(i.SEC.size() == 0) continue;a = i.SEC[0];b = *(--(i.SEC.end()));st.modify(a,b+1,i.FST);cerr << a <<" "<< b <<" "<< i.FST << endl;}rep(i,n)cout << st.query(i,i+1) << (i == n-1?"\n":" ");}