結果
問題 |
No.318 学学学学学
|
ユーザー |
![]() |
提出日時 | 2018-07-09 13:21:51 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 261 ms / 2,000 ms |
コード長 | 3,063 bytes |
コンパイル時間 | 1,402 ms |
コンパイル使用メモリ | 115,836 KB |
実行使用メモリ | 20,736 KB |
最終ジャッジ日時 | 2024-06-22 18:34:51 |
合計ジャッジ時間 | 5,977 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <cmath> #include <iostream> #include <vector> #include <queue> #include <deque> #include <map> #include <set> #include <stack> #include <tuple> #include <bitset> #include <algorithm> #include <functional> #include <utility> #include <iomanip> #define int long long int #define rep(i, n) for(int i = 0; i < (n); ++i) using namespace std; typedef pair<int, int> P; const int INF = 1e15; const int MOD = 1e9+7; template <typename T> class lazy_segment_tree{ private: static int calc_size(int n){ int m = 1; while(m < n){ m *= 2; } return m; } void eval(int i, int l, int r){ if(lazy[i] != -1){ node[i] = lazy[i]; if(r - l > 1){ lazy[i * 2 + 1] = lazy[i]; lazy[i * 2 + 2] = lazy[i]; } lazy[i] = -1; } } void update(int s, int t, int x, int i, int l, int r){ eval(i, l, r); if(t <= l || r <= s){ return; } if(s <= l && r <= t){ lazy[i] = x; eval(i, l, r); return; } int m = l + (r - l) / 2; update(s, t, x, 2 * i + 1, l, m); update(s, t, x, 2 * i + 2, m, r); node[i] = f(node[2 * i + 1], node[2 * i + 2]); } T query(int s, int t, int i, int l, int r){ eval(i, l, r); if(t <= l || r <= s){ return init; } if(s <= l && r <= t){ return node[i]; } int m = l + (r - l) / 2; T vl = query(s, t, i * 2 + 1, l, m); T vr = query(s, t, i * 2 + 2, m, r); return f(vl, vr); } public: int n; vector<T> node, lazy; T init; function<T(T, T)> f; lazy_segment_tree(int n, T init, function<T(T, T)> f) : n(calc_size(n)), node(calc_size(n) * 2, init) , lazy(calc_size(n) * 2, -1), init(init), f(f) {} T query(int s, int t){ return query(s, t, 0, 0, n); } void update(int s, int t, int x){ update(s, t, x, 0, 0, n); } }; signed main(){ int n; cin >> n; vector<int> a(n); rep(i, n) cin >> a[i]; map<int, int> left, right; rep(i, n){ if(left.find(a[i]) != left.end()){ continue; } left.emplace(a[i], i); } for(int i = n-1; i >= 0; i--){ if(right.find(a[i]) != right.end()){ continue; } right.emplace(a[i], i); } lazy_segment_tree<int> lst(n, 0, [](int a, int b){return a+b;}); sort(a.begin(), a.end()); a.erase(unique(a.begin(), a.end()), a.end()); rep(i, (int)a.size()){ lst.update(left[a[i]], right[a[i]]+1, a[i]); } rep(i, n-1){ cout << lst.query(i, i+1) << " "; } cout << lst.query(n-1, n) << endl; return 0; }