結果
問題 | No.318 学学学学学 |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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;