結果
問題 | No.318 学学学学学 |
ユーザー |
|
提出日時 | 2017-10-06 21:21:25 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 239 ms / 2,000 ms |
コード長 | 2,125 bytes |
コンパイル時間 | 877 ms |
コンパイル使用メモリ | 92,384 KB |
実行使用メモリ | 16,952 KB |
最終ジャッジ日時 | 2024-06-22 18:21:43 |
合計ジャッジ時間 | 4,826 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include<cstdio>#include<iostream>#include<algorithm>#include<string>#include<cstring>#include<queue>#include<vector>#include<functional>#include<cmath>#include<map>#include<stack>#include<set>#include<numeric>#include<limits>#include<iterator>#define all(x) (x).begin(),(x).end()#define rall(x) (x).rbegin(),(x).rend()#define rep(i,n) for(int i=0; i<n; i++)#define FOR(i,a,n) for(int i=a; i<n; i++)using namespace std;typedef long long ll;typedef pair<int, int> pi;typedef pair<ll, ll> pl;typedef pair<ll, char> plc;const int MAX_N = 1 << 18;int n,sz;ll node[MAX_N], lazy[MAX_N];struct LazySegmentTree {LazySegmentTree(int n) {sz = 1;while (n > sz )sz *= 2;for (int i = 0; i < 2 * sz - 1; i++)lazy[i] = -1;}void lazy_evaluate_node(int k, int l, int r) {if (lazy[k] != -1) {node[k] = lazy[k] * (r - l);if (r - l > 1) {lazy[k * 2 + 1] = lazy[k];lazy[k * 2 + 2] = lazy[k];}lazy[k] = -1;}}void update(int a, int b, ll v, int k = 0, int l = 0, int r = sz) {lazy_evaluate_node(k, l, r);if (r <= a || b <= l)return;if (a <= l && r <= b) {lazy[k] = v;lazy_evaluate_node(k, l, r);}else {update(a, b, v, k * 2 + 1, l, (l + r) / 2);update(a, b, v, k * 2 + 2, (l + r) / 2, r);node[k] = node[k * 2 + 1] + node[k * 2 + 2];}}ll get(int a, int b, int k = 0, int l = 0, int r = sz) {lazy_evaluate_node(k, l, r);if (r <= a || b <= l)return 0;if (a <= l && r <= b)return node[k];ll x = get(a, b, k * 2 + 1, l, (l + r) / 2);ll y = get(a, b, k * 2 + 2, (l + r) / 2, r);return x + y;}};int main(){cin >> n;vector<int> a(n);rep(i, n)cin >> a[i];map<int, int>left, right;rep(i, n) {if (left.count(a[i]) == 0)left[a[i]] = i;}for (int i = n - 1; i >= 0; i--) {if (right.count(a[i]) == 0) {right[a[i]] = i;}}LazySegmentTree seg(n);rep(i, n)seg.update(i,i+1,a[i]);for (auto v : left) {if (right.count(v.first)) {seg.update(v.second, right[v.first] + 1, v.first);}}rep(i, n)printf("%d ",(int)seg.get(i,i+1));printf("\n");return 0;}