結果
問題 | No.318 学学学学学 |
ユーザー |
![]() |
提出日時 | 2020-11-13 19:06:44 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 123 ms / 2,000 ms |
コード長 | 4,084 bytes |
コンパイル時間 | 1,734 ms |
コンパイル使用メモリ | 179,144 KB |
実行使用メモリ | 13,236 KB |
最終ジャッジ日時 | 2024-07-22 20:15:02 |
合計ジャッジ時間 | 6,024 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h>//#include <atcoder/all>//using namespace atcoder;#pragma GCC target ("avx2")#pragma GCC optimization ("O3")#pragma GCC optimization ("unroll-loops")const double pi = 3.141592653589793238462643383279;using namespace std;//typedef//------------------------------------------typedef vector<int> VI;typedef vector<VI> VVI;typedef vector<string> VS;typedef pair<int, int> PII;typedef pair<long long, long long> PLL;typedef pair<int, PII> TIII;typedef long long LL;typedef unsigned long long ULL;typedef vector<LL> VLL;typedef vector<VLL> VVLL;//container util//------------------------------------------#define ALL(a) (a).begin(), (a).endf()#define RALL(a) (a).rbegin(), (a).rend()#define PB push_back#define MP make_pair#define SZ(a) int((a).size())#define SQ(a) ((a) * (a))#define EACH(i, c) for (typeof((c).begin()) i = (c).begin(); i != (c).endf(); ++i)#define EXIST(s, e) ((s).find(e) != (s).endf())#define SORT(c) sort((c).begin(), (c).endf())//repetition//------------------------------------------#define FOR(i, s, n) for (int i = s; i < (int)n; ++i)#define REP(i, n) FOR(i, 0, n)#define MOD 1000000007#define rep(i, a, b) for (int i = a; i < (b); ++i)#define trav(a, x) for (auto &a : x)#define all(x) x.begin(), x.end()typedef long long ll;typedef pair<int, int> pii;typedef vector<int> vi;#define chmin(x, y) x = min(x, y)#define chmax(x, y) x = max(x, y)const double EPS = 1e-4, PI = acos(-1);//ここから編集typedef string::const_iterator State;/* 区間変更, 区間和 */template<typename T>struct LazySegmentTree{const int INF = numeric_limits<int>::max();int n0;vector<T> node;vector<pair<T, int>> lazy; /* 値, 時間 */LazySegmentTree(vector<T> &v){int n = v.size();n0 = 1;while(n0 < n) n0 <<= 1;node.resize(2*n0-1);lazy.assign(2*n0-1, make_pair(INF, 0));for(int i=0; i<n; i++) node[i+n0-1] = v[i];for(int i=n0-2; i>=0; i--) node[i] = node[i*2+1] + node[i*2+2];}void eval(int k, int t){if(lazy[k].first == INF) return;if(lazy[k].second > t) return;if(k < n0-1){if(lazy[k*2+1].second < t){lazy[k*2+1] = lazy[k];}if(lazy[k*2+2].second < t){lazy[k*2+2] = lazy[k];}}node[k] = lazy[k].first;lazy[k] = make_pair(INF, 0);}void update(int a, int b, T x, int k, int t, ll l, ll r){eval(k, t);if(a <= l && r <= b){if(lazy[k].second < t) lazy[k] = make_pair(x, t);eval(k, t);}else if(a < r && l < b) {update(a, b, x, k*2+1, t, l, (l+r)/2);update(a, b, x, k*2+2, t, (l+r)/2, r);node[k] = node[k*2+1] + node[k*2+2];}}void update(int l, int r, T x, int t) { update(l, r, x, 0, t, 0, n0); }T query(int a, int b, int k, int t, ll l, ll r){eval(k, t);if(r <= a || b <= l) return 0;else if(a <= l && r <= b){return node[k];}else{T vl = query(a, b, k*2+1, t, l, (l+r)/2);T vr = query(a, b, k*2+2, t, (l+r)/2, r);return vl+vr;}}T query(int l, int r, int t) { return query(l, r, 0, t, 0, n0); }inline T operator[](int a) { return query(a, a + 1); }};int main() {cin.tie(0);ios::sync_with_stdio(false);cout << fixed << setprecision(15);int n; cin >> n;vector<ll> a(n);REP(i,n) cin >> a[i];vector<int> v;REP(i,n) v.push_back(a[i]);sort(all(v));v.erase(unique(all(v)), v.end());vector<vector<int>> tmp(v.size());REP(i,n){int id = lower_bound(all(v), a[i]) - v.begin();if(tmp[id].size() <= 1) tmp[id].push_back(i);else {tmp[id][1] = i;}}vector<int> t(n, 0);LazySegmentTree<int> seg(t);for(int i=0; i<v.size(); i++){if(tmp[i].size() == 1){seg.update(tmp[i][0], tmp[i][0]+1, v[i], i+1);}else{seg.update(tmp[i][0], tmp[i][1]+1, v[i], i+1);}}REP(i,n){if(i) cout << " ";cout << seg.query(i, i+1, v.size());}cout << endl;return 0;}