結果
問題 | No.318 学学学学学 |
ユーザー | 👑 はまやんはまやん |
提出日時 | 2017-05-24 12:47:26 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 193 ms / 2,000 ms |
コード長 | 2,860 bytes |
コンパイル時間 | 2,041 ms |
コンパイル使用メモリ | 179,244 KB |
実行使用メモリ | 22,700 KB |
最終ジャッジ日時 | 2023-09-04 20:42:56 |
合計ジャッジ時間 | 5,970 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 17 ms
12,120 KB |
testcase_01 | AC | 29 ms
13,148 KB |
testcase_02 | AC | 33 ms
13,732 KB |
testcase_03 | AC | 24 ms
12,944 KB |
testcase_04 | AC | 30 ms
13,136 KB |
testcase_05 | AC | 188 ms
22,616 KB |
testcase_06 | AC | 151 ms
17,104 KB |
testcase_07 | AC | 128 ms
15,248 KB |
testcase_08 | AC | 112 ms
14,464 KB |
testcase_09 | AC | 92 ms
13,820 KB |
testcase_10 | AC | 72 ms
12,392 KB |
testcase_11 | AC | 193 ms
22,700 KB |
testcase_12 | AC | 128 ms
17,212 KB |
testcase_13 | AC | 106 ms
15,344 KB |
testcase_14 | AC | 90 ms
14,264 KB |
testcase_15 | AC | 83 ms
13,168 KB |
testcase_16 | AC | 67 ms
12,056 KB |
testcase_17 | AC | 107 ms
17,208 KB |
testcase_18 | AC | 98 ms
17,344 KB |
testcase_19 | AC | 107 ms
17,132 KB |
testcase_20 | AC | 64 ms
12,416 KB |
testcase_21 | AC | 6 ms
11,164 KB |
testcase_22 | AC | 6 ms
11,360 KB |
testcase_23 | AC | 6 ms
11,280 KB |
testcase_24 | AC | 5 ms
11,280 KB |
testcase_25 | AC | 6 ms
11,280 KB |
testcase_26 | AC | 6 ms
11,332 KB |
testcase_27 | AC | 6 ms
11,180 KB |
testcase_28 | AC | 6 ms
11,204 KB |
ソースコード
#include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<b;i++) using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); } //--------------------------------------------------------------------------------------------------- typedef long long ll; template<class V, int NV> struct LazySegTree { // [L,R) #define def 0 #define ldef -1 V comp(V l, V r) { return l + r; } void setLazy(int i, V v) { lazy[i] = v; } void push(int k, int l, int r) { if (lazy[k] != ldef) { // modify------------------------------ dat[k] = lazy[k] * (r - l); // ------------------------------------ if (r - l > 1) { setLazy(k * 2 + 1, lazy[k]); setLazy(k * 2 + 2, lazy[k]); } setLazy(k, ldef); } } vector<V> dat, lazy; LazySegTree() { dat.resize(NV * 2, def); lazy.resize(NV * 2, ldef); } void update(int a, int b, V v, int k, int l, int r) { push(k, l, r); if (r <= a || b <= l) return; if (a <= l && r <= b) { setLazy(k, v); push(k, l, r); } else { update(a, b, v, k * 2 + 1, l, (l + r) / 2); update(a, b, v, k * 2 + 2, (l + r) / 2, r); dat[k] = comp(dat[k * 2 + 1], dat[k * 2 + 2]); } } V get(int a, int b, int k, int l, int r) { push(k, l, r); if (r <= a || b <= l) return def; if (a <= l && r <= b) return dat[k]; auto x = get(a, b, k * 2 + 1, l, (l + r) / 2); auto y = get(a, b, k * 2 + 2, (l + r) / 2, r); return comp(x, y); } void update(int a, int b, V v) { update(a, b, v, 0, 0, NV); } V get(int a, int b) { return get(a, b, 0, 0, NV); } }; /*--------------------------------------------------------------------------------------------------- ∧_∧ ∧_∧ (´<_` ) Welcome to My Coding Space! ( ´_ゝ`) / ⌒i / \ | | / / ̄ ̄ ̄ ̄/ | __(__ニつ/ _/ .| .|____ \/____/ (u ⊃ ---------------------------------------------------------------------------------------------------*/ int N; int A[101010]; //--------------------------------------------------------------------------------------------------- LazySegTree<ll, 1 << 18> st; void _main() { cin >> N; rep(i, 0, N) cin >> A[i]; rep(i, 0, N) st.update(i, i + 1, A[i]); map<int, vector<int>> m; rep(i, 0, N) m[A[i]].push_back(i); for (auto p : m) { int i = p.first; auto v = p.second; int mi, ma; mi = ma = v[0]; for (int j : v) mi = min(mi, j), ma = max(ma, j); //printf("[%d %d]\n", mi, ma); st.update(mi, ma + 1, i); } rep(i, 0, N) printf("%lld ", st.get(i, i + 1)); printf("\n"); }