結果
問題 | No.318 学学学学学 |
ユーザー |
![]() |
提出日時 | 2020-06-11 21:33:21 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 799 ms / 2,000 ms |
コード長 | 2,980 bytes |
コンパイル時間 | 3,188 ms |
コンパイル使用メモリ | 80,040 KB |
実行使用メモリ | 72,032 KB |
最終ジャッジ日時 | 2024-06-24 03:21:36 |
合計ジャッジ時間 | 16,143 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
import java.util.*;import java.io.*;public class Main {public static void main (String[] args) throws Exception {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));int n = Integer.parseInt(br.readLine());SegmentTree st = new SegmentTree(n + 1);TreeMap<Integer, ArrayList<Integer>> map = new TreeMap<>();String[] second = br.readLine().split(" ", n);for (int i = 0; i < n; i++) {int x = Integer.parseInt(second[i]);if (!map.containsKey(x)) {map.put(x, new ArrayList<>());}map.get(x).add(i);st.set(i, x);}for (int x : map.keySet()) {ArrayList<Integer> list = map.get(x);int left = list.get(0);int right = list.get(list.size() - 1);st.update(left, right, x);}st.updateAll();StringBuilder sb = new StringBuilder();for (int i = 0; i < n; i++) {if (i > 0) {sb.append(" ");}sb.append(st.getCurrent(i));}System.out.println(sb);}}class SegmentTree {int size;int base;int[] tree;public SegmentTree(int size) {this.size = size;base = 1;while (base < size) {base <<= 1;}tree = new int[base * 2 - 1];}public void set(int idx, int value) {tree[idx + base - 1] = value;}public int getCurrent(int idx) {return tree[idx + base - 1];}public int get(int idx) {return getTree(idx + base - 1);}private int getTree(int idx) {if (idx == 0) {return tree[idx];}int ans;if (idx % 2 == 1) {ans = getTree((idx - 1) / 2);} else {ans = getTree((idx - 1) / 2);}if (ans == 0) {return tree[idx];} else {return ans;}}public void updateAll() {updateAll(0, 0);}private void updateAll(int idx, int value) {if (value > 0) {tree[idx] = value;}if (idx >= base - 1) {return;}updateAll(2 * idx + 1, tree[idx]);updateAll(2 * idx + 2, tree[idx]);}public void update(int min, int max, int value) {update(min, max, value, 0, 0, base);}private void update(int min, int max, int value, int idx, int left, int right) {if (min >= right || max < left) {return;}if (min <= left && right - 1 <= max) {tree[idx] = value;return;}update(min, max, value, 2 * idx + 1, left, (left + right) / 2);update(min, max, value, 2 * idx + 2, (left + right) / 2, right);if (tree[idx] > 0) {int tmp = tree[idx];tree[idx] = 0;update(left, min - 1, tmp, idx, left, right);update(max + 1, right - 1, tmp, idx, left, right);}}}