結果
問題 | No.449 ゆきこーだーの雨と雪 (4) |
ユーザー |
|
提出日時 | 2016-11-22 21:31:18 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 1,379 ms / 5,000 ms |
コード長 | 2,436 bytes |
コンパイル時間 | 4,340 ms |
コンパイル使用メモリ | 82,132 KB |
実行使用メモリ | 89,708 KB |
最終ジャッジ日時 | 2024-09-22 10:30:24 |
合計ジャッジ時間 | 51,161 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 43 |
ソースコード
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[]>() {@Overridepublic int compare(int[] arg0, int[] arg1) {if (arg0[1] != arg1[1])return Integer.compare(arg0[1], arg1[1]);elsereturn -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));}}