結果
問題 | No.318 学学学学学 |
ユーザー | kura197 |
提出日時 | 2022-01-08 11:18:05 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 347 ms / 2,000 ms |
コード長 | 3,687 bytes |
コンパイル時間 | 3,099 ms |
コンパイル使用メモリ | 217,608 KB |
実行使用メモリ | 25,956 KB |
最終ジャッジ日時 | 2024-04-26 19:13:42 |
合計ジャッジ時間 | 8,564 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 19 ms
6,816 KB |
testcase_01 | AC | 40 ms
7,808 KB |
testcase_02 | AC | 50 ms
8,320 KB |
testcase_03 | AC | 32 ms
6,944 KB |
testcase_04 | AC | 45 ms
7,936 KB |
testcase_05 | AC | 347 ms
25,956 KB |
testcase_06 | AC | 314 ms
19,716 KB |
testcase_07 | AC | 224 ms
17,492 KB |
testcase_08 | AC | 179 ms
15,804 KB |
testcase_09 | AC | 143 ms
14,656 KB |
testcase_10 | AC | 106 ms
13,448 KB |
testcase_11 | AC | 316 ms
25,828 KB |
testcase_12 | AC | 202 ms
19,732 KB |
testcase_13 | AC | 165 ms
17,568 KB |
testcase_14 | AC | 135 ms
15,740 KB |
testcase_15 | AC | 112 ms
14,664 KB |
testcase_16 | AC | 87 ms
13,520 KB |
testcase_17 | AC | 175 ms
19,656 KB |
testcase_18 | AC | 148 ms
19,724 KB |
testcase_19 | AC | 173 ms
19,672 KB |
testcase_20 | AC | 69 ms
13,412 KB |
testcase_21 | AC | 2 ms
6,940 KB |
testcase_22 | AC | 2 ms
6,940 KB |
testcase_23 | AC | 2 ms
6,940 KB |
testcase_24 | AC | 2 ms
6,940 KB |
testcase_25 | AC | 2 ms
6,944 KB |
testcase_26 | AC | 2 ms
6,940 KB |
testcase_27 | AC | 2 ms
6,944 KB |
testcase_28 | AC | 2 ms
6,940 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; #define REP(i, n) for(int i=0; i<n; i++) #define REPi(i, a, b) for(int i=int(a); i<int(b); i++) #define MEMS(a,b) memset(a,b,sizeof(a)) #define mp make_pair #define MOD(a, m) ((a % m + m) % m) template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; } template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; } const ll MOD = 1e9+7; template<class S, S (*op)(S, S), S (*init)(), class F, S (*mapping)(F, S), F (*composition)(F, F), F (*id)()> class LazySegmentTree{ ll n; vector<S> node; vector<F> lazy; vector<bool> lazyFlag; public: LazySegmentTree(vector<S> v){ int size = v.size(); n = 1; while(n < size) n *= 2; node.resize(2*n-1, init()); lazy.resize(2*n-1, id()); lazyFlag.resize(2*n-1, false); for(int i = 0; i < size; i++){ node[n-1+i] = v[i]; } for(int i = n-2; i >= 0; i--){ node[i] = op(node[2*i+1], node[2*i+2]); } } // k番目のノードについて遅延評価 void eval(int k, int l, int r){ if(lazyFlag[k]){ if(r - l > 1){ lazy[2*k+1] = composition(lazy[2*k+1], lazy[k]); lazy[2*k+2] = composition(lazy[2*k+2], lazy[k]); lazyFlag[2*k+1] = lazyFlag[2*k+2] = true; } node[k] = mapping(lazy[k], node[k]); lazy[k] = id(); lazyFlag[k] = false; } } // 区間更新 // update val in [a, b] --> update(a, b+1) void update(int a, int b, F x, int k=0, int l=0, int r=-1){ if(r < 0) r = n; eval(k, l, r); if(b <= l || r <= a) return; if(a <= l && r <= b){ lazy[k] = composition(lazy[k], x); lazyFlag[k] = true; 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] = op(node[2*k+1], node[2*k+2]); } } void abs_update(int idx, S val){ idx += n-1; node[idx] = val; while(idx > 0){ idx = (idx-1)/2; node[idx] = op(node[2*idx+1], node[2*idx+2]); } } // get val in [a, b] --> get_val(a, b+1) S get_val(int a, int b, int k=0, int l=0, int r=-1){ if(r < 0) r = n; if(b <= l || r <= a) return init(); eval(k, l, r); if(a <= l && r <= b) return node[k]; S vl = get_val(a, b, 2*k+1, l, (l+r)/2); S vr = get_val(a, b, 2*k+2, (l+r)/2, r); return op(vl, vr); } }; struct S { ll x; int len; }; /// 例 S op(S lhs, S rhs){ return S{lhs.x + rhs.x, lhs.len + rhs.len}; } S init(){ return S{0, 0}; } using F = long long; S mapping(F x, S s){ return S{x * s.len, s.len}; } F composition(F lhs, F rhs){ return rhs; } F id(){ return 0; } int main(){ int N; cin >> N; vector<ll> A(N); for(auto& a : A) cin >> a; map<ll, int> left, right; auto update_left = [&](ll key, int val){ if(left.count(key) == 0) left[key] = val; else chmin(left[key], val); }; REP(i,N){ update_left(A[i], i); right[A[i]] = i; } vector<S> vec(N, S{0, 1}); LazySegmentTree<S, op, init, F, mapping, composition, id> stree(vec); for(auto& [a, L] : left){ auto R = right[a]; stree.update(L, R+1, a); } REP(i,N){ auto [b, _] = stree.get_val(i, i+1); cout << b << " "; } cout << "\n"; return 0; }