結果

問題 No.992 最長増加部分列の数え上げ
ユーザー htensai
提出日時 2020-05-01 10:40:30
言語 Java
(openjdk 23)
結果
TLE  
実行時間 -
コード長 1,326 bytes
コンパイル時間 2,709 ms
コンパイル使用メモリ 79,484 KB
実行使用メモリ 136,200 KB
最終ジャッジ日時 2024-12-23 13:28:35
合計ジャッジ時間 75,080 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27 TLE * 15
権限があれば一括ダウンロードができます

ソースコード

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

import java.util.*;
public class Main {
    static final int MOD = 1000000007;
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        ArrayList<TreeMap<Integer, Integer>> dp = new ArrayList<>();
        dp.add(new TreeMap<>());
        dp.get(0).put(Integer.MIN_VALUE, 1);
        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            int left = 0;
            int right = dp.size();
            while (right - left > 1) {
                int m = (left + right) / 2;
                boolean flag = true;
                if (dp.get(m).firstKey() < x) {
                    left = m;
                } else {
                    right = m;
                }
            }
            int count = 0;
            for (Map.Entry<Integer, Integer> entry : dp.get(left).entrySet()) {
                if (entry.getKey() < x) {
                    count += entry.getValue();
                    count %= MOD;
                } else {
                    break;
                }
            }
            if (dp.size() <= left + 1) {
                dp.add(new TreeMap<>());
            }
            if (dp.get(left + 1).containsKey(x)) {
                dp.get(left + 1).put(x, (dp.get(left + 1).get(x) + count) % MOD);
            } else {
                dp.get(left + 1).put(x, count);
            }
        }
        int total = 0;
        for (int x : dp.get(dp.size() - 1).values()) {
            total += x;
            total %= MOD;
        }
        System.out.println(total);
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0