結果
問題 | No.449 ゆきこーだーの雨と雪 (4) |
ユーザー | 37zigen |
提出日時 | 2016-11-22 21:31:18 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 1,350 ms / 5,000 ms |
コード長 | 2,436 bytes |
コンパイル時間 | 5,788 ms |
コンパイル使用メモリ | 90,028 KB |
実行使用メモリ | 92,364 KB |
最終ジャッジ日時 | 2023-10-23 16:02:49 |
合計ジャッジ時間 | 52,390 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 139 ms
56,916 KB |
testcase_01 | AC | 141 ms
57,068 KB |
testcase_02 | AC | 136 ms
57,140 KB |
testcase_03 | AC | 225 ms
58,168 KB |
testcase_04 | AC | 224 ms
56,780 KB |
testcase_05 | AC | 223 ms
58,316 KB |
testcase_06 | AC | 216 ms
57,988 KB |
testcase_07 | AC | 225 ms
58,072 KB |
testcase_08 | AC | 220 ms
58,032 KB |
testcase_09 | AC | 229 ms
58,356 KB |
testcase_10 | AC | 209 ms
58,112 KB |
testcase_11 | AC | 219 ms
58,004 KB |
testcase_12 | AC | 1,274 ms
80,776 KB |
testcase_13 | AC | 1,241 ms
83,240 KB |
testcase_14 | AC | 1,334 ms
86,004 KB |
testcase_15 | AC | 1,253 ms
83,508 KB |
testcase_16 | AC | 1,306 ms
83,804 KB |
testcase_17 | AC | 1,308 ms
83,244 KB |
testcase_18 | AC | 1,253 ms
80,844 KB |
testcase_19 | AC | 1,332 ms
84,332 KB |
testcase_20 | AC | 1,328 ms
84,212 KB |
testcase_21 | AC | 1,248 ms
83,940 KB |
testcase_22 | AC | 1,276 ms
84,964 KB |
testcase_23 | AC | 1,202 ms
80,688 KB |
testcase_24 | AC | 1,290 ms
86,576 KB |
testcase_25 | AC | 1,248 ms
76,200 KB |
testcase_26 | AC | 1,315 ms
77,924 KB |
testcase_27 | AC | 1,276 ms
81,944 KB |
testcase_28 | AC | 1,264 ms
85,852 KB |
testcase_29 | AC | 1,347 ms
83,988 KB |
testcase_30 | AC | 1,238 ms
83,408 KB |
testcase_31 | AC | 1,298 ms
83,428 KB |
testcase_32 | AC | 1,350 ms
85,236 KB |
testcase_33 | AC | 1,319 ms
86,168 KB |
testcase_34 | AC | 1,347 ms
83,132 KB |
testcase_35 | AC | 1,246 ms
82,892 KB |
testcase_36 | AC | 1,337 ms
83,524 KB |
testcase_37 | AC | 1,102 ms
92,364 KB |
testcase_38 | AC | 1,309 ms
87,580 KB |
testcase_39 | AC | 1,326 ms
88,604 KB |
testcase_40 | AC | 1,293 ms
88,308 KB |
testcase_41 | AC | 1,164 ms
88,440 KB |
testcase_42 | AC | 1,123 ms
90,112 KB |
testcase_43 | AC | 1,298 ms
79,556 KB |
testcase_44 | AC | 1,122 ms
76,588 KB |
testcase_45 | AC | 993 ms
89,328 KB |
ソースコード
package yukicoder; import java.util.Arrays; import java.util.Comparator; import java.util.HashMap; import java.util.Scanner; public class Q449 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] l = new int[n]; for (int i = 0; i < n; ++i) { l[i] = sc.nextInt(); } int t = sc.nextInt(); int[] rank = new int[n]; HashMap<String, Integer> map = new HashMap<>(); int count = 0; String[] name = new String[t]; char[] p = new char[t]; int[] scores = new int[t]; HashMap<String, Integer> curScore = new HashMap<>(); for (int i = 0; i < t; ++i) { name[i] = sc.next(); p[i] = sc.next().toCharArray()[0]; if (p[i] == '?') { scores[i] = Integer.MAX_VALUE / 10; } else { int star = l[p[i] - 'A']; if (!map.containsKey(name)) { map.put(name[i], count++); } ++rank[p[i] - 'A']; if (curScore.containsKey(name[i])) { scores[i] += curScore.get(name[i]); } scores[i] += score(map.get(name[i]), rank[p[i] - 'A'], star); curScore.put(name[i], scores[i]); } } int[][] ord = new int[t][]; for (int i = 0; i < t; ++i) { ord[i] = new int[] { i, scores[i] }; } Arrays.sort(ord, new Comparator<int[]>() { @Override public int compare(int[] arg0, int[] arg1) { if (arg0[1] != arg1[1]) return Integer.compare(arg0[1], arg1[1]); else return -Integer.compare(arg0[0], arg1[0]); } }); FenwickTree ft = new FenwickTree(t + 1); for (int i = 0; i < t; ++i) { scores[ord[i][0]] = i + 1; } curScore.clear(); for (int i = 0; i < t; ++i) { if (p[i] == '?') { System.out.println(ft.sum(t) - ft.sum(curScore.get(name[i])) + 1); } else { if (curScore.containsKey(name[i])) { ft.add(curScore.get(name[i]), -1); } ft.add(scores[i], 1); curScore.put(name[i], scores[i]); } } } static void tr(Object... objects) { System.out.println(Arrays.deepToString(objects)); } static class FenwickTree { int n; int[] dat; public FenwickTree(int n) { this.n = n + 1; dat = new int[this.n]; } void add(int k, int val) { while (k < n) { dat[k] += val; k += k & -k; } } int sum(int k) { int sum = 0; while (k > 0) { sum += dat[k]; k -= k & -k; } return sum; } } static int score(int id, int rank, int star) { return (int) (50 * star + (50 * star) / (0.8 + 0.2 * rank)); } }