結果
問題 | No.945 YKC饅頭 |
ユーザー | kitakitalily |
提出日時 | 2019-12-08 21:18:14 |
言語 | Java21 (openjdk 21) |
結果 |
RE
|
実行時間 | - |
コード長 | 6,808 bytes |
コンパイル時間 | 4,592 ms |
コンパイル使用メモリ | 82,152 KB |
実行使用メモリ | 111,480 KB |
最終ジャッジ日時 | 2024-06-10 06:25:42 |
合計ジャッジ時間 | 32,611 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 97 ms
45,920 KB |
testcase_01 | AC | 84 ms
45,592 KB |
testcase_02 | RE | - |
testcase_03 | RE | - |
testcase_04 | RE | - |
testcase_05 | RE | - |
testcase_06 | RE | - |
testcase_07 | RE | - |
testcase_08 | AC | 94 ms
45,760 KB |
testcase_09 | RE | - |
testcase_10 | RE | - |
testcase_11 | RE | - |
testcase_12 | AC | 125 ms
47,016 KB |
testcase_13 | RE | - |
testcase_14 | RE | - |
testcase_15 | RE | - |
testcase_16 | AC | 101 ms
45,784 KB |
testcase_17 | RE | - |
testcase_18 | RE | - |
testcase_19 | AC | 108 ms
46,028 KB |
testcase_20 | RE | - |
testcase_21 | RE | - |
testcase_22 | RE | - |
testcase_23 | AC | 128 ms
46,772 KB |
testcase_24 | RE | - |
testcase_25 | RE | - |
testcase_26 | RE | - |
testcase_27 | AC | 100 ms
45,916 KB |
testcase_28 | AC | 99 ms
45,756 KB |
testcase_29 | AC | 93 ms
44,620 KB |
testcase_30 | AC | 97 ms
45,364 KB |
testcase_31 | AC | 336 ms
55,756 KB |
testcase_32 | AC | 577 ms
71,228 KB |
testcase_33 | RE | - |
testcase_34 | RE | - |
testcase_35 | RE | - |
testcase_36 | RE | - |
testcase_37 | RE | - |
testcase_38 | RE | - |
testcase_39 | AC | 590 ms
67,068 KB |
testcase_40 | AC | 574 ms
72,752 KB |
testcase_41 | AC | 517 ms
67,900 KB |
testcase_42 | RE | - |
testcase_43 | RE | - |
testcase_44 | RE | - |
testcase_45 | RE | - |
testcase_46 | AC | 373 ms
61,960 KB |
testcase_47 | RE | - |
testcase_48 | RE | - |
testcase_49 | AC | 565 ms
72,528 KB |
testcase_50 | RE | - |
testcase_51 | RE | - |
testcase_52 | AC | 1,062 ms
101,288 KB |
testcase_53 | RE | - |
testcase_54 | RE | - |
testcase_55 | AC | 1,056 ms
101,016 KB |
testcase_56 | AC | 428 ms
73,300 KB |
testcase_57 | AC | 297 ms
65,700 KB |
testcase_58 | AC | 704 ms
87,408 KB |
testcase_59 | AC | 746 ms
87,148 KB |
testcase_60 | AC | 612 ms
76,632 KB |
testcase_61 | AC | 710 ms
89,176 KB |
testcase_62 | RE | - |
testcase_63 | AC | 311 ms
64,880 KB |
testcase_64 | AC | 678 ms
77,832 KB |
testcase_65 | AC | 707 ms
76,900 KB |
testcase_66 | AC | 713 ms
77,820 KB |
testcase_67 | AC | 705 ms
89,276 KB |
testcase_68 | RE | - |
testcase_69 | AC | 569 ms
72,112 KB |
testcase_70 | AC | 547 ms
71,500 KB |
testcase_71 | AC | 577 ms
71,700 KB |
testcase_72 | AC | 688 ms
87,720 KB |
testcase_73 | RE | - |
ソースコード
import java.util.*; import java.io.*; public class Main { static int size = 200000; static long[] fac = new long[size]; static long[] finv = new long[size]; static long[] inv = new long[size]; static int mod = 1000000007; static int INF = Integer.MAX_VALUE; public static void main(String[] args){ FastScanner scanner = new FastScanner(); int n = scanner.nextInt(); int m = scanner.nextInt(); int[] l = new int[m]; int[] r = new int[m]; String[] s = new String[m]; for(int i = 0; i < m; i++){ l[i] = scanner.nextInt()-1; r[i] = scanner.nextInt()-1; s[i] = scanner.next(); } TreeSet<Integer> set = new TreeSet<Integer>(); for(int i = 0; i < n; i++){ set.add(i); } TreeSet<Integer> rm = new TreeSet<Integer>(); String[] ans = new String[n]; for(int i = 0; i < m; i++){ int it = set.ceiling(l[i]); while(it <= r[i] && !set.isEmpty()){ if(!rm.contains(it)){ rm.add(it); ans[it] = s[i]; } set.remove(it); it++; } //System.out.println(set); } int cnty = 0; int cntk = 0; int cntc = 0; for(int i = 0; i < n; i++){ if(ans[i] == null) continue; if(ans[i].equals("Y")){ cnty++; }else if(ans[i].equals("K")){ cntk++; }else if(ans[i].equals("C")){ cntc++; } } System.out.println(cnty+ " " + cntk + " " + cntc); } //繰り返し二乗法 public static long pow(long x, long n){ long ans = 1; while(n > 0){ if((n & 1) == 1){ ans = ans * x; ans %= mod; } x = x * x % mod; n >>= 1; } return ans; } public static long div(long x, long y){ return (x*pow(y, mod-2))%mod; } //fac, inv, finvテーブルの初期化、これ使う場合はinitComb()で初期化必要 public static void initComb(){ fac[0] = finv[0] = inv[0] = fac[1] = finv[1] = inv[1] = 1; for (int i = 2; i < size; ++i) { fac[i] = fac[i - 1] * i % mod; inv[i] = mod - (mod / i) * inv[(int) (mod % i)] % mod; finv[i] = finv[i - 1] * inv[i] % mod; } } //nCk % mod public static long comb(int n, int k){ return fac[n] * finv[k] % mod * finv[n - k] % mod; } //n! % mod public static long fact(int n){ return fac[n]; } //(n!)^-1 with % mod public static long finv(int n){ return finv[n]; } /** * 0-indexed BinaryIndexTree * 区間加算あり * */ static class BIT { private int n; private long[] bit; public BIT(int n) { this.n = n; bit = new long[n + 2]; } public void accumulate(int begin, int end, long num) { accumulate(begin, num); accumulate(end, -num); } private void accumulate(int index, long num) { index++; while (index <= n + 1) { bit[index] += num; index += index & -index; } } private long sum(int i) { long s = 0; while (i > 0) { s += bit[i]; i -= i & -i; } return s; } public long get(int index) { return sum(index + 1); } public void set(int index, long num) { accumulate(index, index + 1, num - get(index)); } public String toString() { long[] value = new long[n]; for (int i = 0; i < n; i++) { value[i] = get(i); } return Arrays.toString(value); } } static class Pair implements Comparable<Pair>{ int first, second; Pair(int a, int b){ first = a; second = b; } @Override public boolean equals(Object o){ if (this == o) return true; if (!(o instanceof Pair)) return false; Pair p = (Pair) o; return first == p.first && second == p.second; } @Override public int compareTo(Pair p){ return first == p.first ? second - p.second : first - p.first; //firstで昇順にソート //return (first == p.first ? second - p.second : first - p.first) * -1; //firstで降順にソート //return second == p.second ? first - p.first : second - p.second;//secondで昇順にソート //return (second == p.second ? first - p.first : second - p.second)*-1;//secondで降順にソート //return first * 1.0 / second > p.first * 1.0 / p.second ? 1 : -1; // first/secondの昇順にソート //return first * 1.0 / second < p.first * 1.0 / p.second ? 1 : -1; // first/secondの降順にソート //return second * 1.0 / first > p.second * 1.0 / p.first ? 1 : -1; // second/firstの昇順にソート //return second * 1.0 / first < p.second * 1.0 / p.first ? 1 : -1; // second/firstの降順にソート //return Math.atan2(second, first) > Math.atan2(p.second, p.first) ? 1 : -1; // second/firstの昇順にソート //return first + second > p.first + p.second ? 1 : -1; //first+secondの昇順にソート //return first + second < p.first + p.second ? 1 : -1; //first+secondの降順にソート //return first - second < p.first - p.second ? 1 : -1; //first-secondの降順にソート //return second - first < p.second - p.first ? -1 : 1; //second-firstの昇順にソート //return Math.atan2(second,first) > Math.atan2(p.second, p.first) ? 1 : -1; } } private static class FastScanner { private final InputStream in = System.in; private final byte[] buffer = new byte[1024]; private int ptr = 0; private int buflen = 0; private boolean hasNextByte() { if (ptr < buflen) { return true; }else{ ptr = 0; try { buflen = in.read(buffer); } catch (IOException e) { e.printStackTrace(); } if (buflen <= 0) { return false; } } return true; } private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;} private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;} public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();} public String next() { if (!hasNext()) throw new NoSuchElementException(); StringBuilder sb = new StringBuilder(); int b = readByte(); while(isPrintableChar(b)) { sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } public long nextLong() { if (!hasNext()) throw new NoSuchElementException(); long n = 0; boolean minus = false; int b = readByte(); if (b == '-') { minus = true; b = readByte(); } if (b < '0' || '9' < b) { throw new NumberFormatException(); } while(true){ if ('0' <= b && b <= '9') { n *= 10; n += b - '0'; }else if(b == -1 || !isPrintableChar(b)){ return minus ? -n : n; }else{ throw new NumberFormatException(); } b = readByte(); } } public int nextInt() { long nl = nextLong(); if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException(); return (int) nl; } public double nextDouble() { return Double.parseDouble(next());} } }