結果

問題 No.318 学学学学学
ユーザー cormoran
提出日時 2016-09-01 23:06:41
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 179 ms / 2,000 ms
コード長 4,153 bytes
コンパイル時間 2,196 ms
コンパイル使用メモリ 180,300 KB
実行使用メモリ 15,232 KB
最終ジャッジ日時 2024-06-22 17:51:59
合計ジャッジ時間 5,338 ms
ジャッジサーバーID
(参考情報)
judge1 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
using ll = long long;
#define rep(i, j) for(int i=0; i < (int)(j); i++)
#define repeat(i, j, k) for(int i = (j); i < (int)(k); i++)
#define all(v) v.begin(),v.end()
#define debug(x) cerr << #x << " : " << x << endl
template<class T> bool set_min(T &a, const T &b) { return a > b ? a = b, true : false; }
template<class T> bool set_max(T &a, const T &b) { return a < b ? a = b, true : false; }
// vector
template<class T> istream& operator >> (istream &is , vector<T> &v) { for(T &a : v) is >> a; return is; }
template<class T> ostream& operator << (ostream &os , const vector<T> &v) { for(const T &t : v) os << "\t" << t; return os << endl; }
// pair
template<class T, class U> ostream& operator << (ostream &os , const pair<T, U> &v) { return os << "<" << v.first << " " << v.second << ">"; }
const int INF = 1 << 30;
const ll INFL = 1LL << 60;
using Index = int;
template<typename Data>
class SegmentTree{
public:
int size; // arraysize (2^k)
vector<Data> data; // size -1 to end
SegmentTree(int n){
size = 1;
while(size < n) size *= 2;
data.resize( 2 * size - 1, -1);
}
void update(Index a, Index b, Data val){
update(a, b, 0, 0, size, val);
}
Data query(Index i){
return query(i, 0, 0, size);
}
void debug_tree() {
int dep = ceil(log2(size));
rep(i, dep + 1) {
debug_tree(0, i);
cout << endl;
}
}
private:
void debug_tree(Index i, int dep) {
if(dep == 0) {
cout << data[i] << " ";
} else {
debug_tree(left_child(i), dep - 1);
debug_tree(right_child(i), dep - 1);
cout << " | ";
}
}
// [a, b) , i Node, [l, r) Node[i]
void update(Index a, Index b, Index i, Index l, Index r, Data val){
if(val < 0) return;
//cerr << "UPDATE [" << a << "," << b << "]" << " " << i << " [" << l << "," << r << ") VAL" << val << endl;
if(out_of_range(a, b, l, r)); // do nothing
else if(in_range(a, b, l, r)) {
data[i] = val;
} else {
Index m = (l + r) / 2;
if(l < a) {
update(l, a, left_child(i), l, m, data[i]);
update(l, a, right_child(i), m, r, data[i]);
}
if(b < r) {
update(b, r, left_child(i), l, m, data[i]);
update(b, r, right_child(i), m, r, data[i]);
}
update(a, b, left_child(i), l, m, val);
update(a, b, right_child(i), m, r, val);
data[i] = -1;
}
}
Data query(Index a, Index i, Index l, Index r){
//cerr << "QUERY " << a << "now " << i << " [" << l << "," << r << ")" << endl;
if(data[i] >= 0) return data[i];
assert(l + 1 < r);
Index m = (l + r) / 2;
if(a < m) return query(a, left_child(i), l, m);
else return query(a, right_child(i), m, r);
}
bool out_of_range(Index a, Index b, Index l, Index r) { return r <= a or b <= l; }
bool in_range(Index a, Index b, Index l, Index r) { return a <= l and r <= b; }
Index left_child(Index i) { return i * 2 + 1; }
Index right_child(Index i) { return i * 2 + 2; }
};
class Solver {
public:
int N;
bool solve() {
cin >> N;
map<int, vector<int>> mp;
rep(i, N) {
int a; cin >> a;
mp[a].push_back(i);
}
SegmentTree<int> st(N);
for(auto &p: mp) {
if(p.second.size() == 1) p.second.push_back(p.second.front());
sort(all(p.second));
st.update(p.second.front(), p.second.back() + 1, p.first);
//st.debug_tree();
}
rep(i, N) {
cout << st.query(i) << (i == N - 1 ? "\n": " ");
}
return 0;
}
};
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
Solver s;
s.solve();
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0