結果
問題 |
No.318 学学学学学
|
ユーザー |
|
提出日時 | 2025-01-14 01:43:14 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,773 bytes |
コンパイル時間 | 8,737 ms |
コンパイル使用メモリ | 270,568 KB |
実行使用メモリ | 15,232 KB |
最終ジャッジ日時 | 2025-01-14 01:43:30 |
合計ジャッジ時間 | 14,842 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 WA * 1 |
other | AC * 8 WA * 11 RE * 7 |
ソースコード
#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>0) { 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) { if(pos >= n) return; if(node[pos] != 0) { node[2*pos] = node[pos]; node[2*pos+1] = node[pos]; } all_prop(2*pos); all_prop(2*pos+1); } }; 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; } } 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; }