結果
問題 | 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;}