結果

問題 No.318 学学学学学
ユーザー toma
提出日時 2019-09-24 22:43:16
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 209 ms / 2,000 ms
コード長 3,299 bytes
コンパイル時間 2,111 ms
コンパイル使用メモリ 187,412 KB
実行使用メモリ 22,144 KB
最終ジャッジ日時 2024-09-19 13:29:30
合計ジャッジ時間 7,186 ms
ジャッジサーバーID
(参考情報)
judge5 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include"bits/stdc++.h"
using namespace std;
#define REP(k,m,n) for(int (k)=(m);(k)<(n);(k)++)
#define rep(i,n) REP((i),0,(n))
using ll = long long;
template<typename Monoid, typename OperatorMonoid = Monoid>
class LazySegmentTree {
private:
using F = function<Monoid(Monoid, Monoid)>;
using G = function<Monoid(Monoid, OperatorMonoid, int)>;
using H = function<OperatorMonoid(OperatorMonoid, OperatorMonoid)>;
int sz; //
vector<Monoid> data;
vector<OperatorMonoid> lazy;
const F f; // 2(data-data-)
const G g; // ,(lazy->data(data,lazy,len))
const H h; //  (query->lazy(lazy,query_value))
const Monoid M1; //  (data)
const OperatorMonoid OM0; // (lazy)
void propagate(int idx, int len) {
// lenlazy[idx]
if (lazy[idx] != OM0) {
if (idx < sz) {
lazy[(idx << 1) | 0] = h(lazy[(idx << 1) | 0], lazy[idx]);
lazy[(idx << 1) | 1] = h(lazy[(idx << 1) | 1], lazy[idx]);
}
data[idx] = g(data[idx], lazy[idx], len);
lazy[idx] = OM0;
}
}
Monoid update_impl(int a, int b, const OperatorMonoid& val, int idx, int l, int r) {
propagate(idx, r - l);
if (r <= a || b <= l)return data[idx];
else if (a <= l && r <= b) {
lazy[idx] = h(lazy[idx], val);
propagate(idx, r - l);
return data[idx];
}
else return data[idx] = f(
update_impl(a, b, val, (idx << 1) | 0, l, (l + r) >> 1),
update_impl(a, b, val, (idx << 1) | 1, (l + r) >> 1, r)
);
}
Monoid query_impl(int a, int b, int idx, int l, int r) {
propagate(idx, r - l);
if (r <= a || b <= l)return M1;
else if (a <= l && r <= b)return data[idx];
else return f(
query_impl(a, b, (idx << 1) | 0, l, (l + r) >> 1),
query_impl(a, b, (idx << 1) | 1, (l + r) >> 1, r)
);
}
public:
// init
LazySegmentTree(int n, const F f, const G g, const H h,
const Monoid& M1, const OperatorMonoid OM0)
:f(f), g(g), h(h), M1(M1), OM0(OM0) {
sz = 1;
while (sz < n)sz <<= 1;
data.assign(2 * sz, M1);
lazy.assign(2 * sz, OM0);
}
void build(const vector<Monoid>& vals) {
rep(idx, vals.size())data[idx + sz] = vals[idx];
for (int idx = sz - 1; idx > 0; idx--) {
data[idx] = f(data[(idx << 1) | 0], data[(idx << 1) | 1]);
}
}
Monoid update(int a, int b, const OperatorMonoid& val) {
return update_impl(a, b, val, 1, 0, sz);
}
Monoid query(int a, int b) {
return query_impl(a, b, 1, 0, sz);
}
Monoid operator[](const int& idx) {
return query(idx, idx + 1);
}
};
int main()
{
// input
ll n;
cin >> n;
vector<ll> a(n);
rep(i, n)cin >> a[i];
// seg init
auto f = [](ll l, ll r) {return l + r; };
auto g = [](ll data, ll lazy, int siz) {return lazy; };
auto h = [](ll lazy, ll query) {return query; };
LazySegmentTree<ll> seg(n, f, g, h, 0, 0);
// mapper
map<ll, set<ll>> mp;
rep(i, n)mp[a[i]].insert(i);
// query
for (auto itr : mp) {
ll val = itr.first;
ll l = *itr.second.begin();
ll r = *(--itr.second.end());
seg.update(l, r + 1, val);
}
rep(i, n)cout << seg[i] << " ";
cout << endl;
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0