結果
問題 | No.1705 Mode of long array |
ユーザー | Asahi |
提出日時 | 2023-11-27 02:48:03 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 1,329 ms / 3,000 ms |
コード長 | 16,328 bytes |
コンパイル時間 | 3,396 ms |
コンパイル使用メモリ | 98,000 KB |
実行使用メモリ | 108,140 KB |
最終ジャッジ日時 | 2023-11-27 02:48:46 |
合計ジャッジ時間 | 42,526 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 121 ms
57,440 KB |
testcase_01 | AC | 145 ms
57,452 KB |
testcase_02 | AC | 125 ms
57,556 KB |
testcase_03 | AC | 194 ms
58,212 KB |
testcase_04 | AC | 168 ms
57,856 KB |
testcase_05 | AC | 201 ms
57,424 KB |
testcase_06 | AC | 263 ms
61,408 KB |
testcase_07 | AC | 310 ms
61,368 KB |
testcase_08 | AC | 291 ms
61,420 KB |
testcase_09 | AC | 266 ms
61,316 KB |
testcase_10 | AC | 272 ms
61,260 KB |
testcase_11 | AC | 295 ms
61,372 KB |
testcase_12 | AC | 265 ms
61,424 KB |
testcase_13 | AC | 863 ms
89,208 KB |
testcase_14 | AC | 690 ms
87,384 KB |
testcase_15 | AC | 601 ms
70,336 KB |
testcase_16 | AC | 757 ms
86,920 KB |
testcase_17 | AC | 589 ms
76,516 KB |
testcase_18 | AC | 518 ms
73,652 KB |
testcase_19 | AC | 753 ms
77,784 KB |
testcase_20 | AC | 615 ms
79,344 KB |
testcase_21 | AC | 752 ms
91,204 KB |
testcase_22 | AC | 978 ms
97,636 KB |
testcase_23 | AC | 317 ms
67,356 KB |
testcase_24 | AC | 335 ms
67,524 KB |
testcase_25 | AC | 326 ms
67,340 KB |
testcase_26 | AC | 316 ms
67,340 KB |
testcase_27 | AC | 323 ms
67,504 KB |
testcase_28 | AC | 320 ms
67,324 KB |
testcase_29 | AC | 330 ms
67,384 KB |
testcase_30 | AC | 318 ms
67,440 KB |
testcase_31 | AC | 319 ms
67,332 KB |
testcase_32 | AC | 325 ms
67,252 KB |
testcase_33 | AC | 734 ms
99,060 KB |
testcase_34 | AC | 726 ms
99,124 KB |
testcase_35 | AC | 689 ms
99,464 KB |
testcase_36 | AC | 766 ms
99,112 KB |
testcase_37 | AC | 717 ms
99,104 KB |
testcase_38 | AC | 729 ms
98,940 KB |
testcase_39 | AC | 705 ms
98,848 KB |
testcase_40 | AC | 712 ms
99,140 KB |
testcase_41 | AC | 710 ms
99,236 KB |
testcase_42 | AC | 689 ms
98,912 KB |
testcase_43 | AC | 1,234 ms
107,256 KB |
testcase_44 | AC | 1,312 ms
108,008 KB |
testcase_45 | AC | 1,252 ms
108,084 KB |
testcase_46 | AC | 1,329 ms
108,140 KB |
testcase_47 | AC | 1,237 ms
107,448 KB |
testcase_48 | AC | 1,169 ms
104,496 KB |
testcase_49 | AC | 942 ms
105,272 KB |
testcase_50 | AC | 929 ms
104,404 KB |
testcase_51 | AC | 973 ms
105,152 KB |
testcase_52 | AC | 953 ms
103,012 KB |
testcase_53 | AC | 930 ms
104,508 KB |
ソースコード
import java.util.*; import java.io.*; import java.math.*; import java.util.stream.*; import java.util.function.*; class Main implements Runnable { class SegmentTree <T> { private int n ; private T init ; private T [] tree ; private int size ; private BinaryOperator<T> op ; @SuppressWarnings ("unchecked") SegmentTree(int size , T init , BinaryOperator<T> op) { this.size = size; this.init = init ; this.op = op ; n = 1 ; while(n <= size) n *= 2 ; this.tree = (T []) new Object[2 * n]; for(int i = 0 ; i < 2 * n ; i ++ ) tree[i] = init ; } public void update(int index , T value) { index += n ; tree[index] = value ; while(index > 0) { index /= 2 ; tree[index] = op.apply(tree[2 * index] , tree[2 * index + 1]); } } public T query(int l , int r){ l += n ; r += n ; T res = init ; while(l < r){ if(l % 2 == 1){ res = op.apply(res , tree[l]) ; l ++ ; } l /= 2 ; if(r % 2 == 1){ res = op.apply(res , tree[r - 1]) ; r -- ; } r /= 2 ; } return res ; } public String debug() { StringBuilder sb = new StringBuilder(); for(int i = n ; i < n + size ; i ++ ) sb.append(tree[i]+" "); return sb.toString() ; } } class Compress<T> { private TreeSet<T> order ; private Map<T,Integer> comp ; private int count ; Compress(List<T> L) { this.order = new TreeSet<>(L) ; this.comp = new HashMap<>(); this.count = 0 ; for(T v : order) comp.put(v , count++); } public int get(T value) { return comp.get(value); } public int size() { return order.size(); } } record P(long fi , long se) { } public void solve(){ long n = in.nextLong() ; int m = in.nextInt(); long [] a = in.nextLong(m); Set<Long> S = new HashSet<>(); for(long i = 1 ; i <= m ; i ++) S.add(i); List<Trio<Integer,Long,Long>> query = new ArrayList<>(); int q = in.nextInt(); for(int i = 0 ; i < q ; i ++){ int t = in.nextInt() ; long x = in.nextLong() , y = in.nextLong(); query.add(new Trio<>(t , x , y)); S.add(x); } Compress<Long> Comp = new Compress<>(new ArrayList<>(S)); SegmentTree<P> seg = new SegmentTree<>(Comp.size() , new P(0 , 0) , (x , y) -> { if(x.se < y.se) return y ; else if(x.se > y.se) return x; return x.fi < y.fi ? y : x ; }); for(long i = 1 ; i <= m ; i ++) { int id = Comp.get(i); long count = seg.query(id , id + 1).se ; seg.update(id , new P(id , count + a[(int)i - 1])); } for(int i = 0 ; i < q ; i ++) { var que = query.get(i); int id = Comp.get(que.se); long count = seg.query(id , id + 1).se ; if(que.fi == 1) { seg.update(id , new P(id , count + que.th)); } if(que.fi == 2) { seg.update(id , new P(id , count - que.th)); } if(que.fi == 3) { print(seg.query(0 , Comp.size()).fi); } } } public record Pair<T,S> (T fi , S se) { public String toString() { return "("+fi+","+se+")"; } } public record Trio<T,S,U>(T fi , S se , U th) { public String toString() { return "("+fi+","+se+","+th+")"; } } public PrintWriter out = new PrintWriter(System.out); public In in = new In(); public static final int mod7 = 1000000007; public static final int mod9 = 998244353; public static final int inf = (1 << 30); public static final long lnf = (1L << 60); public static final String yes = "Yes"; public static final String no = "No" ; public static final int [] dy4 = {-1,0,1,0}; public static final int [] dx4 = {0,1,0,-1}; public static final int [] dy8 = {-1,-1,-1,0,1,1,1,0}; public static final int [] dx8 = {-1,0,1,1,1,0,-1,-1}; public boolean isOver(int y , int x , int h , int w) { return y < 0 || x < 0 || y >= h || x >= w ; } public void swap(int [] array , int l , int r) { int tmp = array[l] ; array[l] = array[r] ; array[r] = tmp ; } public void swap(long [] array , int l , int r) { long tmp = array[l] ; array[l] = array[r] ; array[r] = tmp ; } public String swap(String string , int l , int r) { StringBuilder m = new StringBuilder(string) ; m.setCharAt(l, string.charAt(r)); m.setCharAt(r, string.charAt(l)); return m.toString(); } public String binarytoString(int a , int len) { String b = Integer.toBinaryString(a); while(b.length() < len) b = "0" + b ; return b ; } public String binarytoString(long a , int len) { String b = Long.toBinaryString(a); while(b.length() < len) b = "0" + b ; return b ; } public <T extends Comparable<T>> int LowCountClosed(List<T> A , T key) { return upperbound(A, key); } public <T extends Comparable<T>> int LowCountOpen(List<T> A , T key) { return lowerbound(A, key); } public <T extends Comparable<T>> int HighCountClosed(List<T> A , T key) { return A.size() - lowerbound(A, key); } public <T extends Comparable<T>> int HighCountOpen(List<T> A , T key) { return A.size() - upperbound(A, key); } // [) public <T extends Comparable<T>> int CountClosedOpen(List<T> A, T a, T b) { return lowerbound(A, b) - lowerbound(A, a); } // [] public <T extends Comparable<T>> int CountClosedClosed(List<T> A, T a, T b) { return upperbound(A, b) - lowerbound(A, a); } // (] public <T extends Comparable<T>> int CountOpenClosed(List<T> A, T a, T b) { return upperbound(A, b) - upperbound(A, a); } // () public <T extends Comparable<T>> int CountOpenOpen(List<T> A, T a, T b) { return lowerbound(A, b) - upperbound(A, a); } private <T extends Comparable<T>> int lowerbound(List<T> A, T key) { int left = 0 , right = A.size(); while (left < right) { int mid = (left + right) / 2; if (A.get(mid).compareTo(key) < 0) left = mid + 1; else right = mid; } return right; } private <T extends Comparable<T>> int upperbound(List<T> A, T key) { int left = 0 , right = A.size(); while (left < right) { int mid = (left + right) / 2; if (A.get(mid).compareTo(key) <= 0) left = mid + 1; else right = mid; } return right; } public Integer [] toInteger(int [] a) { return Arrays.stream(a).boxed().toArray(Integer[]::new); } public Long [] toLong(long [] a) { return Arrays.stream(a).boxed().toArray(Long[]::new); } public Double [] toDouble(double [] a) { return Arrays.stream(a).boxed().toArray(Double[]::new); } public <T> List<T> ArrayList(T [] a) { return Arrays.stream(a).collect(Collectors.toCollection(ArrayList::new)); } public <T> HashSet<T> HashSet(T [] a) { return Arrays.stream(a).collect(Collectors.toCollection(HashSet::new)); } public <T> TreeSet<T> TreeSet(T [] a) { return Arrays.stream(a).collect(Collectors.toCollection(TreeSet::new)); } public <T> Deque<T> Deque(T [] a) { return Arrays.stream(a).collect(Collectors.toCollection(ArrayDeque::new)); } public <T> PriorityQueue<T> PriorityQueue(T [] a) { return Arrays.stream(a).collect(Collectors.toCollection(PriorityQueue::new)); } public <T> List <T> [] ArrayList(int n) { @SuppressWarnings("unchecked") List<T> [] G = new ArrayList[n]; for(int i = 0 ; i < n ; i ++ ) G[i] = new ArrayList<>(); return G ; } public <T> HashSet <T> [] HashSet(int n) { @SuppressWarnings("unchecked") HashSet<T> [] G = new HashSet[n]; for(int i = 0 ; i < n ; i ++ ) G[i] = new HashSet<>() ; return G ; } public <T> TreeSet <T> [] TreeSet(int n) { @SuppressWarnings("unchecked") TreeSet<T> [] G = new TreeSet[n]; for(int i = 0 ; i < n ; i ++ ) G[i] = new TreeSet<>() ; return G ; } public <T> TreeSet <T> [] TreeSet(int n , Comparator<? super T> comparator) { @SuppressWarnings("unchecked") TreeSet<T> [] G = new TreeSet[n]; for(int i = 0 ; i < n ; i ++ ) G[i] = new TreeSet<>(comparator) ; return G ; } public <T> Deque <T> [] Deque(int n) { @SuppressWarnings("unchecked") Deque<T> [] G = new ArrayDeque[n]; for(int i = 0 ; i < n ; i ++ ) G[i] = new ArrayDeque<>(); return G ; } public <T> PriorityQueue <T> [] PriorityQueue(int n) { @SuppressWarnings("unchecked") PriorityQueue<T> [] G = new PriorityQueue[n]; for(int i = 0 ; i < n ; i ++ ) G[i] = new PriorityQueue<>(); return G ; } public <T> PriorityQueue <T> [] PriorityQueue(int n , Comparator<? super T> comparator) { @SuppressWarnings("unchecked") PriorityQueue<T> [] G = new PriorityQueue[n]; for(int i = 0 ; i < n ; i ++ ) G[i] = new PriorityQueue<>(comparator); return G ; } public <K,V> HashMap <K,V> [] HashMap(int n) { @SuppressWarnings("unchecked") HashMap<K,V> [] G = new HashMap[n]; for(int i = 0 ; i < n ; i ++ ) G[i] = new HashMap<>() ; return G ; } public <K,V> TreeMap <K,V> [] TreeMap(int n) { @SuppressWarnings("unchecked") TreeMap<K,V> [] G = new TreeMap[n]; for(int i = 0 ; i < n ; i ++ ) G[i] = new TreeMap<>() ; return G ; } public <K,V> TreeMap <K,V> [] TreeMap(int n , Comparator<? super K> comparator) { @SuppressWarnings("unchecked") TreeMap<K,V> [] G = new TreeMap[n]; for(int i = 0 ; i < n ; i ++ ) G[i] = new TreeMap<>(comparator) ; return G ; } //---------------------------------------------------------------------------------------// @SuppressWarnings("unchecked") public <T> void print(T ... data) { StringBuilder pr = new StringBuilder(); for(var temp : data) pr.append(temp+" "); out.println(pr.toString()); out.flush(); } public void print(String [][] array) { StringBuilder pr = new StringBuilder(); for(var temp : array) { for(var data : temp) { pr.append(data+" "); } pr.append("\n"); } if(0 < pr.length()) pr.deleteCharAt(pr.length() - 1); out.println(pr.toString()); out.flush(); } public void print(char [][] array) { StringBuilder pr = new StringBuilder(); for(var temp : array) { for(var data : temp) { pr.append(data); } pr.append("\n"); } if(0 < pr.length()) pr.deleteCharAt(pr.length() - 1); out.println(pr.toString()); out.flush(); } public <T> void print(Collection<T> collection) { StringBuilder pr = new StringBuilder(); for(T data : collection) pr.append(data +" "); out.println(pr.toString()); out.flush(); } public static void main(String ... args) { new Thread(null, new Main(), "", Runtime.getRuntime().maxMemory()).start(); } public void run() { solve(); out.flush(); } } class In { private final InputStream in = System.in; private final Scanner sc = new Scanner(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; } private 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()); } public char nextChar() { return next().charAt(0); } public BigInteger nexBigInteger() { return sc.nextBigInteger(); } public int [] nextInt(int n) { int [] array = new int[n]; for(int i = 0 ; i < n ; i ++) { array[i] = nextInt(); } return array ; } public int [][] nextInt(int n , int m) { int [][] array = new int[n][m]; for(int i = 0 ; i < n ; i ++) { array[i] = nextInt(m); } return array ; } public long [] nextLong(int n) { long [] array = new long[n]; for(int i = 0 ; i < n ; i ++) { array[i] = nextLong(); } return array ; } public long [][] nextLong(int n , int m) { long [][] array = new long[n][m]; for(int i = 0 ; i < n ; i ++) { array[i] = nextLong(m); } return array ; } public double [] nextDouble(int n) { double [] array = new double[n]; for(int i = 0 ; i < n ; i ++) { array[i] = nextDouble(); } return array ; } public String [] next(int n) { String [] array = new String[n]; for(int i = 0 ; i < n ; i ++) { array[i] = next(); } return array ; } public String [][] next(int n , int m) { String [][] array = new String[n][m]; for(int i = 0 ; i < n ; i ++) { array[i] = next(m); } return array ; } public char [] nextChar(int n) { char [] array = new char[n]; String string = next() ; for(int i = 0 ; i < n ; i ++) { array[i] = string.charAt(i); } return array ; } public char [][] nextChar(int n , int m) { char [][] array = new char[n][m]; for(int i = 0 ; i < n ; i ++) { array[i] = nextChar(m); } return array ; } }