結果
問題 | No.1705 Mode of long array |
ユーザー |
|
提出日時 | 2023-11-27 02:48:03 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 1,356 ms / 3,000 ms |
コード長 | 16,328 bytes |
コンパイル時間 | 4,026 ms |
コンパイル使用メモリ | 101,456 KB |
実行使用メモリ | 92,916 KB |
最終ジャッジ日時 | 2024-09-26 12:07:37 |
合計ジャッジ時間 | 41,180 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 51 |
ソースコード
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 ;}}