結果
問題 | No.318 学学学学学 |
ユーザー | tubo28 |
提出日時 | 2015-12-11 00:21:09 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 192 ms / 2,000 ms |
コード長 | 2,628 bytes |
コンパイル時間 | 2,574 ms |
コンパイル使用メモリ | 156,240 KB |
実行使用メモリ | 13,860 KB |
最終ジャッジ日時 | 2023-09-04 16:37:33 |
合計ジャッジ時間 | 6,872 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 12 ms
4,380 KB |
testcase_01 | AC | 24 ms
5,324 KB |
testcase_02 | AC | 29 ms
5,480 KB |
testcase_03 | AC | 20 ms
4,620 KB |
testcase_04 | AC | 25 ms
4,920 KB |
testcase_05 | AC | 190 ms
13,860 KB |
testcase_06 | AC | 183 ms
8,936 KB |
testcase_07 | AC | 156 ms
7,296 KB |
testcase_08 | AC | 133 ms
6,304 KB |
testcase_09 | AC | 116 ms
5,444 KB |
testcase_10 | AC | 88 ms
4,644 KB |
testcase_11 | AC | 192 ms
13,604 KB |
testcase_12 | AC | 130 ms
8,980 KB |
testcase_13 | AC | 110 ms
7,216 KB |
testcase_14 | AC | 92 ms
6,484 KB |
testcase_15 | AC | 75 ms
5,100 KB |
testcase_16 | AC | 56 ms
4,380 KB |
testcase_17 | AC | 138 ms
8,796 KB |
testcase_18 | AC | 84 ms
8,840 KB |
testcase_19 | AC | 140 ms
8,872 KB |
testcase_20 | AC | 39 ms
4,376 KB |
testcase_21 | AC | 2 ms
4,380 KB |
testcase_22 | AC | 1 ms
4,376 KB |
testcase_23 | AC | 2 ms
4,380 KB |
testcase_24 | AC | 2 ms
4,380 KB |
testcase_25 | AC | 1 ms
4,376 KB |
testcase_26 | AC | 2 ms
4,376 KB |
testcase_27 | AC | 2 ms
4,376 KB |
testcase_28 | AC | 1 ms
4,384 KB |
ソースコード
#define _CRT_SECURE_NO_WARNINGS // #define _GLIBCXX_DEBUG #include <bits/stdc++.h> using namespace std; template<class T> ostream &operator << (ostream &os, const vector<T> &); template<size_t n, class...T> typename enable_if<(n>=sizeof...(T))>::type _ot(ostream &, const tuple<T...> &){} template<size_t n, class...T> typename enable_if<(n< sizeof...(T))>::type _ot(ostream &os, const tuple<T...> &t){ os << (n == 0 ? "" : " ") << get<n>(t); _ot<n+1>(os, t); } template<class...T> ostream &operator << (ostream &os, const tuple<T...> &t){ _ot<0>(os, t); return os; } template<class T, class U> ostream & operator << (ostream &os, const pair<T,U> &p){ return os << "(" << p.first << ", " << p.second << ") "; } template<class T> ostream &operator << (ostream &os, const vector<T> &v){ for(size_t i = 0; i < v.size(); i++) os << v[i] << (i + 1 == v.size() ? "" : ", "); return os; } #ifdef DEBUG #define dump(...) (cerr << #__VA_ARGS__ << " = " << make_tuple(__VA_ARGS__) \ << " (L : " << __LINE__ << ")" << endl) #else #define dump(...) #endif #define all(c) begin(c), end(c) #define range(i,a,b) for(int i = a; i < (int)(b); i++) #define rep(i,b) range(i,0,b) #define pb push_back #define eb emplace_back #define mp make_pair #define mt make_tuple using ll = long long; // #define int ll using vi = vector<int>; using vvi = vector<vi>; using pii = pair<int,int>; void fastios(){ ios_base::sync_with_stdio(0); cin.tie(0); } int const mod = 1000000007; auto const inf = numeric_limits<int>::max()/8; int n; vi in; vi solve(){ const int B = 300; vi a(n,-1), b(n/B+1,-1); map<int,int> maxPos, minPos; rep(i,n){ if(maxPos.count(in[i])){ maxPos[in[i]] = max(maxPos[in[i]], i); minPos[in[i]] = min(minPos[in[i]], i); } else { maxPos[in[i]] = minPos[in[i]] = i; } } auto assign = [&](int l, int r, int x){ int i = l; while(i < r){ if(i%B == 0 && i + B <= r){ b[i/B] = x; i += B; } else { a[i] = x; i++; } } }; auto get = [&](int i){ return max(a[i], b[i/B]); }; for(auto & p : minPos){ int v = p.first, l = p.second, r = maxPos[v]+1; dump(l,r,v); assign(l,r,v); } vector<int> res(n); rep(i,n) res[i] = get(i); return res; } int main(){ while(cin >> n){ in.resize(n); rep(i,n) cin >> in[i]; vi ans = solve(); rep(i,ans.size()) cout << ans[i] << (i+1==(int)ans.size() ? '\n' : ' '); } }