結果
問題 | No.2422 regisys? |
ユーザー |
![]() |
提出日時 | 2023-08-17 11:45:39 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 1,399 ms / 2,000 ms |
コード長 | 4,480 bytes |
コンパイル時間 | 2,394 ms |
コンパイル使用メモリ | 92,512 KB |
実行使用メモリ | 85,228 KB |
最終ジャッジ日時 | 2024-11-26 08:07:41 |
合計ジャッジ時間 | 33,611 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 61 |
ソースコード
import java.io.*;import java.util.*;import java.util.stream.*;public class Main {public static void main(String[] args) throws Exception {Scanner sc = new Scanner();int n = sc.nextInt();int m = sc.nextInt();Goods[] goods = new Goods[n];for (int i = 0; i < n; i++) {goods[i] = new Goods(i, sc.nextInt());}PriorityQueue<Goods> stock = new PriorityQueue<>();for (int i = 0; i < n; i++) {goods[i].prices[1] = sc.nextInt();stock.add(goods[i]);}PriorityQueue<Integer> normal = new PriorityQueue<>();PriorityQueue<Integer> mma = new PriorityQueue<>();while (m-- > 0) {if (sc.nextInt() == 0) {normal.add(sc.nextInt());} else {mma.add(sc.nextInt());}}TreeSet<Goods> store = new TreeSet<>();while (normal.size() > 0) {int x = normal.poll();while (stock.size() > 0 && stock.peek().prices[0] <= x) {Goods g = stock.poll();g.add();store.add(g);}if (store.size() > 0) {store.pollLast();}}while (stock.size() > 0) {Goods g = stock.poll();g.add();store.add(g);}while (mma.size() > 0) {int x = mma.poll();if (store.size() > 0 && store.first().prices[1] <= x) {store.pollFirst();}}System.out.println(store.size() + stock.size());}static class Goods implements Comparable<Goods> {int idx;int[] prices;int current;public Goods(int idx, int p) {prices = new int[2];this.idx = idx;prices[0] = p;}public void add() {current++;}public int hashCode() {return idx;}public int compareTo(Goods another) {if (prices[current] == another.prices[another.current]) {return idx - another.idx;} else {return prices[current] - another.prices[another.current];}}public boolean equals(Object o) {return hashCode() == o.hashCode();}}}class BinaryIndexedTree {int size;int[] tree;public BinaryIndexedTree(int size) {this.size = size;tree = new int[size];}public void add(int idx, int value) {int mask = 1;while (idx < size) {if ((idx & mask) != 0) {tree[idx] += value;idx += mask;}mask <<= 1;}}public int getSum(int from, int to) {return getSum(to) - getSum(from - 1);}public int getSum(int x) {int mask = 1;int ans = 0;while (x > 0) {if ((x & mask) != 0) {ans += tree[x];x -= mask;}mask <<= 1;}return ans;}}class Utilities {static String arrayToLineString(Object[] arr) {return Arrays.stream(arr).map(x -> x.toString()).collect(Collectors.joining("\n"));}static String arrayToLineString(int[] arr) {return String.join("\n", Arrays.stream(arr).mapToObj(String::valueOf).toArray(String[]::new));}}class Scanner {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));StringTokenizer st = new StringTokenizer("");StringBuilder sb = new StringBuilder();public Scanner() throws Exception {}public int nextInt() throws Exception {return Integer.parseInt(next());}public long nextLong() throws Exception {return Long.parseLong(next());}public double nextDouble() throws Exception {return Double.parseDouble(next());}public int[] nextIntArray() throws Exception {return Stream.of(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();}public String next() throws Exception {while (!st.hasMoreTokens()) {st = new StringTokenizer(br.readLine());}return st.nextToken();}}