結果
問題 | No.318 学学学学学 |
ユーザー |
![]() |
提出日時 | 2016-04-04 10:24:03 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,396 bytes |
コンパイル時間 | 847 ms |
コンパイル使用メモリ | 96,840 KB |
実行使用メモリ | 11,008 KB |
最終ジャッジ日時 | 2024-10-02 13:08:55 |
合計ジャッジ時間 | 4,930 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 22 WA * 4 |
ソースコード
/* -*- coding: utf-8 -*- * * 318.cc: No.318 学学学学学 - yukicoder */ #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<string> #include<vector> #include<map> #include<set> #include<stack> #include<list> #include<queue> #include<deque> #include<algorithm> #include<numeric> #include<utility> #include<complex> #include<functional> using namespace std; /* constant */ const int MAX_N = 100000; const int MAX_E2 = 1 << 18; /* typedef */ typedef map<int,int> mii; template <typename T, const int MAX_E2> struct SegTreeDelay { int n, e2; T nodes[MAX_E2]; SegTreeDelay() {} void init(int _n) { n = _n; for (e2 = 1; e2 < n; e2 <<= 1); memset(nodes, 0, sizeof(nodes)); } T get(int i) { return nodes[e2 - 1 + i]; } void set(int i, T v) { nodes[e2 - 1 + i] = v; } void propagate() { for (int j = 0; j < e2 - 1; j++) if (nodes[j]) { nodes[j * 2 + 1] = nodes[j * 2 + 2] = nodes[j]; nodes[j] = 0; } } void set_range(T v, int r0, int r1, int k, int i0, int i1) { if (r1 <= i0 || i1 <= r0) return; if (r0 <= i0 && i1 <= r1) { nodes[k] = v; return; } int k0 = k * 2 + 1, k1 = k0 + 1; if (nodes[k]) { nodes[k0] = nodes[k1] = nodes[k]; nodes[k] = 0; } int im = (i0 + i1) / 2; set_range(v, r0, r1, k0, i0, im); set_range(v, r0, r1, k1, im, i1); } void set_range(T v, int r0, int r1) { set_range(v, r0, r1, 0, 0, e2); } }; /* global variables */ int as[MAX_N], gs[MAX_N], mings[MAX_N], maxgs[MAX_N]; mii gmap; SegTreeDelay<int,MAX_E2> st; /* subroutines */ /* main */ int main() { int n; cin >> n; for (int i = 0; i < n; i++) { cin >> as[i]; gs[i] = as[i]; } sort(gs, gs + n); int gn = unique(gs, gs + n) - gs; //printf("gn=%d\n", gn); for (int i = 0; i < gn; i++) gmap[gs[i]] = i; memset(mings, -1, sizeof(mings)); memset(maxgs, -1, sizeof(maxgs)); st.init(n); for (int i = 0; i < n; i++) { int gi = gmap[as[i]]; st.set(i, gi); if (mings[gi] < 0 || mings[gi] > i) mings[gi] = i; if (maxgs[gi] < i) maxgs[gi] = i; } for (int i = 0; i < gn; i++) if (mings[i] < maxgs[i]) st.set_range(i, mings[i], maxgs[i] + 1); st.propagate(); for (int i = 0; i < n; i++) { if (i) putchar(' '); printf("%d", gs[st.get(i)]); } putchar('\n'); return 0; }