結果
問題 | No.318 学学学学学 |
ユーザー |
![]() |
提出日時 | 2020-08-20 14:21:40 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 274 ms / 2,000 ms |
コード長 | 2,689 bytes |
コンパイル時間 | 1,820 ms |
コンパイル使用メモリ | 129,492 KB |
最終ジャッジ日時 | 2025-01-13 04:20:53 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <iostream>#include <string>#include <vector>#include <deque>#include <queue>#include <algorithm>#include <set>#include <map>#include <bitset>#include <cmath>#include <functional>#define vv(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))#define vvi vector<vector<int> >#define vvl vector<vector<ll> >#define vll vector<ll>typedef long long int ll;typedef long double ld;using namespace std;int INF = 1000000000;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] = min(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] = min(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 INF;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 min(vl, vr);}};int main(int argc, char const *argv[]) {ll n, a;std::cin >> n;map<ll, vll> mp;LazySegmentTree seg( vector<int>(n, INF) );for(int i=0;i<n;i++){std::cin >> a;if(mp.find(a)==mp.end()) mp.emplace(a, vll{i, i});else{vll p = mp.at(a);p[0] = min(p[0], (ll)i), p[1] = max(p[1], (ll)i);mp.erase(a);mp.emplace(a, p);}}for(auto itr=mp.begin();itr!=mp.end();itr++){//std::cout << (*itr).first << " " << (*itr).second[0] << " " << (*itr).second[1] << '\n';seg.update((*itr).second[0], (*itr).second[1]+1, (*itr).first);}for(int i=0;i<n;i++){std::cout << seg.find(i, i+1) << (i==n-1?"\n":" ");}return 0;}