結果

問題 No.318 学学学学学
ユーザー norioc
提出日時 2020-05-07 12:28:08
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 105 ms / 2,000 ms
コード長 2,121 bytes
コンパイル時間 2,807 ms
コンパイル使用メモリ 180,356 KB
実行使用メモリ 34,960 KB
最終ジャッジ日時 2024-06-22 06:54:39
合計ジャッジ時間 6,275 ms
ジャッジサーバーID
(参考情報)
judge4 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

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

import std;
const segSize = 1 << 20;
int[segSize * 2] seg;
int[segSize * 2] segTime; //
void update(int l, int r, int v, int time) {
l += segSize;
r += segSize;
while (l < r) {
if (l % 2 == 1) {
seg[l] = v;
segTime[l] = time;
l++;
}
l /= 2;
if (r % 2 == 1) {
seg[r - 1] = v;
segTime[r - 1] = time;
r--;
}
r /= 2;
}
}
int get(int ind) {
ind += segSize;
int v = seg[ind];
int time = segTime[ind];
while (true) {
ind /= 2; //
if (ind == 0) break;
if (time < segTime[ind]) { //
v = seg[ind];
time = segTime[ind];
}
}
return v;
}
// ()
void propagate() {
void rec(int ind) {
if (ind * 2 >= seg.length) return;
int lt = ind * 2;
int rt = ind * 2 + 1;
if (segTime[ind] > segTime[lt]) { // :
seg[lt] = seg[ind];
segTime[lt] = segTime[ind];
}
if (segTime[ind] > segTime[rt]) { // :
seg[rt] = seg[ind];
segTime[rt] = segTime[ind];
}
rec(lt);
rec(rt);
}
rec(1);
}
void calc(int[] a) {
int n = cast(int)a.length;
int[int] first, last;
foreach_reverse(i; 0..n) first[a[i]] = i;
foreach (i; 0..n) last[a[i]] = i;
int time = 1;
foreach (k; first.keys.sort) {
int l = first[k];
int r = last[k];
update(l, r + 1, k, time++);
}
propagate();
auto ans = seg[segSize..$].take(n).map!text.join(' ');
writeln(ans);
}
void main() {
read;
auto a = readints;
calc(a);
}
void scan(T...)(ref T a) {
string[] ss = readln.split;
foreach (i, t; T) a[i] = ss[i].to!t;
}
T read(T=string)() { return readln.chomp.to!T; }
T[] reads(T)() { return readln.split.to!(T[]); }
alias readints = reads!int;
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0