結果
問題 | No.318 学学学学学 |
ユーザー |
|
提出日時 | 2018-04-06 23:37:50 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 208 ms / 2,000 ms |
コード長 | 2,204 bytes |
コンパイル時間 | 2,092 ms |
コンパイル使用メモリ | 176,220 KB |
実行使用メモリ | 15,488 KB |
最終ジャッジ日時 | 2024-06-22 18:32:13 |
合計ジャッジ時間 | 5,912 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h>using namespace std;typedef long long ll;int N, Q;const int INF = INT_MAX;struct LazySegmentTree {private:int n;vector<int> node, lazy;vector<bool> lazyFlag;public:LazySegmentTree(vector<int> v) {int sz = (int)v.size();n = 1; while(n < sz) n *= 2;node.resize(2*n-1);lazy.resize(2*n-1, INF);lazyFlag.resize(2*n-1, false);for(int i=0; i<sz; i++) node[i+n-1] = v[i];for(int i=n-2; i>=0; i--) node[i] = node[i*2+1] + node[i*2+2];}void lazyEvaluate(int k, int l, int r) {if(lazyFlag[k]) {node[k] = lazy[k];if(r - l > 1) {lazy[k*2+1] = lazy[k*2+2] = lazy[k];lazyFlag[k*2+1] = lazyFlag[k*2+2] = true;}lazyFlag[k] = false;}}void update(int a, int b, int x, int k=0, int l=0, int r=-1) {if(r < 0) r = n;lazyEvaluate(k, l, r);if(b <= l || r <= a) return;if(a <= l && r <= b) {lazy[k] = x;lazyFlag[k] = true;lazyEvaluate(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] = node[2*k+1] + node[2*k+2];}}int find(int a, int b, int k=0, int l=0, int r=-1) {if(r < 0) r = n;lazyEvaluate(k, l, r);if(b <= l || r <= a) return 0;if(a <= l && r <= b) return node[k];int vl = find(a, b, 2*k+1, l, (l+r)/2);int vr = find(a, b, 2*k+2, (l+r)/2, r);return vl+ vr;}};int main() {cin.tie(0);ios::sync_with_stdio(false);map<int, int> first, last;cin >> N;vector<int> a(N);for(int i=0;i<N;i++)cin >> a[i];for(int i=N-1;i>=0;i--)first[a[i]] = i;for(int i=0;i<N;i++)last[a[i]] = i;LazySegmentTree seg( vector<int>(N, 0));for(int i=0;i<N;i++) {seg.update(i, i+1, a[i]);}for(auto kv : first) {seg.update(kv.second, last[kv.first]+1, kv.first);}for(int i=0;i<N;i++) {cout << seg.find(i, i+1);if(i != N-1)cout << " ";}cout << endl;}