結果
| 問題 | No.318 学学学学学 |
| ユーザー |
 hashiryo
|
| 提出日時 | 2018-10-10 17:29:44 |
| 言語 | C++11（廃止可能性あり） (gcc 13.3.0) |
| 結果 |
AC
|
| 実行時間 | 128 ms / 2,000 ms |
| コード長 | 4,135 bytes |
| コンパイル時間 | 1,065 ms |
| コンパイル使用メモリ | 95,188 KB |
| 実行使用メモリ | 8,192 KB |
| 最終ジャッジ日時 | 2024-06-22 18:44:48 |
| 合計ジャッジ時間 | 4,730 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 26 |
ソースコード
#include <iostream>#include <stdio.h>#include <fstream>#include <algorithm>#include <string>#include <map>#include <set>#include <queue>#include <stack>#include <vector>#include <limits.h>#include <math.h>#include <functional>#include <bitset>#define repeat(i,n) for (long long i = 0; (i) < (n); ++ (i))#define debug(x) cerr << #x << ": " << x << '\n'#define debugArray(x,n) for(long long i = 0; (i) < (n); ++ (i)) cerr << #x << "[" << i << "]: " << x[i] << '\n'#define debugArrayP(x,n) for(long long i = 0; (i) < (n); ++ (i)) cerr << #x << "[" << i << "]: " << x[i].first<< " " << x[i].second << '\n'using namespace std;typedef long long ll;typedef unsigned long long ull;typedef pair<int,int> Pii;typedef vector<int> vint;typedef vector<ll> vll;const ull INF = ULLONG_MAX;const ll MOD = 1e9+7;inline int get_min2pow(int n) {int res = 1;while (res < n)res *= 2;return res;}//遅延評価SegmentTree/////////////lazyの初期値に注意template<typename T>struct delay_segtree {private:int N;vector<T> node, lazy;//例外値 ex)INF,0//-------書くとこ---------------------T default_value = 0;T default_lazy = 0;static inline T merge(const T& u, const T& v) {return u + v;}static inline void lazy_transmit(T& u, const T& v) {u = v;}static inline void node_transmit(T& u,const T& v,int l,int r){u = v;}//------------------------------------// k 番目のノードについて遅延評価を行うvoid eval(int k, int l, int r) {// 遅延配列が空でない場合、自ノード及び子ノードへの// 値の伝播が起こるif (lazy[k] != default_lazy) {node_transmit(node[k], lazy[k],l,r);// 最下段かどうかのチェックをしようif (r - l > 1) {lazy_transmit(lazy[2 * k + 1], lazy[k]);lazy_transmit(lazy[2 * k + 2], lazy[k]);}// 伝播が終わったので、自ノードの遅延配列を空にするlazy[k] = default_lazy;}}public:delay_segtree(int n) {for(N=1;N<n;N*=2);node.resize(2 * N, default_value);lazy.resize(2 * N, default_lazy);}delay_segtree(vector<int> v) {int sz = v.size();for(N=1;N<sz;N*=2);node.resize(2 * N, default_value);lazy.resize(2 * N, default_lazy);for (int i = 0; i < sz; i++)node[i + N - 1] = v[i];for (int i = N - 2; i >= 0; i--)node[i] = merge(node[2 * i + 1], node[2 * i + 2]);}void update(int a, int b, T x, int k = 0, int l = 0, int r = -1) {if (r < 0)r = N;// k 番目のノードに対して遅延評価を行うeval(k, l, r);// 範囲外なら何もしないif (b <= l || r <= a)return;// 完全に被覆しているならば、遅延配列に値を入れた後に評価if (a <= l && r <= b) {lazy_transmit(lazy[k], x);eval(k, l, r);}// そうでないならば、子ノードの値を再帰的に計算して、// 計算済みの値をもらってくるelse {update(a, b, x, 2 * k + 1, l, (l + r) / 2);update(a, b, x, 2 * k + 2, (l + r) / 2, r);node[k] = merge(node[2 * k + 1], node[2 * k + 2]);}}// update k th elementvoid update(int k, T val) {k += N - 1; // leafnode[k] = val;while (k > 0) {k = (k - 1) / 2;node[k] = merge(node[k * 2 + 1], node[k * 2 + 2]);}}// [a, b)T query(int a, int b, int k = 0, int l = 0, int r = -1) {if (r < 0)r = N;eval(k, l, r);if (r <= a or b <= l)return default_value;if (a <= l and r <= b)return node[k];int m = (l + r) / 2;T vl = query(a, b, k * 2 + 1, l, m);T vr = query(a, b, k * 2 + 2, m, r);return merge(vl, vr);}T operator[](const int &k) {//遅延評価をまずしておくquery(k, k + 1);return node[k + N - 1];}};int main(){int n;cin>>n;delay_segtree<ll> b(n);vector<Pii> a(n);repeat(i,n){cin>>a[i].first;a[i].second=i;}sort(a.begin(),a.end());repeat(i,n){int j;for(j=i;j<n&&a[j].first==a[i].first;j++);j--;b.update(a[i].second,a[j].second+1,a[i].first);}repeat(i,n){cout << b[i];cout << (i<n-1? " ":"\n");}return 0;}