結果
問題 | No.318 学学学学学 |
ユーザー | ojisan_IT |
提出日時 | 2018-04-21 10:49:01 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 165 ms / 2,000 ms |
コード長 | 3,418 bytes |
コンパイル時間 | 2,264 ms |
コンパイル使用メモリ | 178,740 KB |
実行使用メモリ | 15,508 KB |
最終ジャッジ日時 | 2023-09-04 21:03:58 |
合計ジャッジ時間 | 5,810 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 12 ms
5,384 KB |
testcase_01 | AC | 24 ms
6,412 KB |
testcase_02 | AC | 30 ms
6,716 KB |
testcase_03 | AC | 20 ms
6,208 KB |
testcase_04 | AC | 25 ms
6,400 KB |
testcase_05 | AC | 165 ms
15,508 KB |
testcase_06 | AC | 155 ms
10,284 KB |
testcase_07 | AC | 128 ms
8,280 KB |
testcase_08 | AC | 109 ms
7,464 KB |
testcase_09 | AC | 90 ms
6,452 KB |
testcase_10 | AC | 67 ms
5,388 KB |
testcase_11 | AC | 160 ms
15,500 KB |
testcase_12 | AC | 110 ms
10,224 KB |
testcase_13 | AC | 96 ms
8,248 KB |
testcase_14 | AC | 86 ms
7,052 KB |
testcase_15 | AC | 74 ms
6,144 KB |
testcase_16 | AC | 60 ms
5,128 KB |
testcase_17 | AC | 92 ms
10,168 KB |
testcase_18 | AC | 84 ms
10,164 KB |
testcase_19 | AC | 91 ms
10,144 KB |
testcase_20 | AC | 43 ms
5,132 KB |
testcase_21 | AC | 3 ms
4,508 KB |
testcase_22 | AC | 3 ms
4,624 KB |
testcase_23 | AC | 3 ms
4,476 KB |
testcase_24 | AC | 3 ms
4,648 KB |
testcase_25 | AC | 3 ms
4,572 KB |
testcase_26 | AC | 3 ms
4,508 KB |
testcase_27 | AC | 3 ms
4,624 KB |
testcase_28 | AC | 3 ms
4,388 KB |
ソースコード
#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 monoid struct 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 tree const M m_id; // identity element of monoid const O o_id; // identity element of operator monoid MM mm; MO mo; OO oo; OI oi; vector<M> m; // monoid array vector<O> o; // operator monoid array SegTree(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":" "); }