結果
問題 | No.318 学学学学学 |
ユーザー |
|
提出日時 | 2025-01-14 02:01:05 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 294 ms / 2,000 ms |
コード長 | 1,833 bytes |
コンパイル時間 | 3,895 ms |
コンパイル使用メモリ | 290,388 KB |
実行使用メモリ | 21,376 KB |
最終ジャッジ日時 | 2025-01-14 02:01:15 |
合計ジャッジ時間 | 9,008 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;using vec = vector<ll>;using mat = vector<vec>;using matx = vector<mat>; using maty = vector<matx>;const int INF = 1073741823;const ll INFl = 1LL << 60;#define rep(i, n) for (int i = 0; i < (int)(n); i++)struct LazySegmentTree {int n;vec node, lazy;LazySegmentTree(vec v) {int sz = v.size();n = 1;while(n < sz) n*=2;node.resize(2*n, 0);lazy.resize(2*n, 0);rep(i, sz) node[i+n] = v[i];}void eval(int pos, int bottom, int top) {if(lazy[pos] > 0) {node[pos] = lazy[pos];if(top-bottom>1) {lazy[pos*2] = lazy[pos];lazy[pos*2+1] = lazy[pos];}lazy[pos] = 0;}}void update(int l, int r, ll x, int pos=1, int bottom=0, int top=-1) {if(top == -1) top=n;eval(pos, bottom, top);if(top <= l || r <= bottom) return;if(l <= bottom && top <= r) {lazy[pos] = x;eval(pos, bottom, top);}else {int mid = (top + bottom)/2;update(l, r, x, pos*2, bottom, mid);update(l, r, x, pos*2+1, mid, top);node[pos] = 0;}}void all_prop(int pos=1, int bottom = 0, int top = -1) {if(top==-1) top = n;eval(pos, bottom, top);if(pos >= n) return;int mid = (bottom+top)/2;all_prop(2*pos, bottom, mid);all_prop(2*pos+1, mid, top);}};int main() {int n; cin >> n;map<ll, ll> l, r;vec A(n);rep(i, n) {ll a; cin >> a; A[i] = a;if(l.count(a)){r[a] = i;}else {l[a] = i;r[a] = i;}}LazySegmentTree tree(A);for(auto p:r) {auto num = p.first;auto R = p.second;auto L = l[num];tree.update(L, R+1, num);}tree.all_prop();rep(i, n) {cout << tree.node[tree.n+i] << " ";}cout << endl;}