結果
問題 |
No.3198 Monotonic Query
|
ユーザー |
![]() |
提出日時 | 2025-08-07 11:55:21 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 288 ms / 3,000 ms |
コード長 | 4,480 bytes |
コンパイル時間 | 2,521 ms |
コンパイル使用メモリ | 81,004 KB |
実行使用メモリ | 53,476 KB |
最終ジャッジ日時 | 2025-08-07 11:55:33 |
合計ジャッジ時間 | 10,878 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
import java.io.*; import java.util.*; import java.util.function.*; import java.util.stream.*; import java.math.*; public class Main { public static void main(String[] args) throws Exception { FastScanner sc = new FastScanner(); int q = sc.nextInt(); int current = 0; SegmentTree st = new SegmentTree(q); StringBuilder sb = new StringBuilder(); while (q-- > 0) { int type = sc.nextInt(); int v = sc.nextInt(); if (type == 1) { st.setValue(current++, v); } else { sb.append(st.getMax(current - v, current)).append("\n"); } } System.out.print(sb); } static class SegmentTree { int size; int[] values; public SegmentTree(int x) { size = 2; while (size < x) { size <<= 1; } values = new int[size * 2 - 1]; } public void setValue(int idx, int v) { values[idx + size - 1] = v; calc((idx + size - 2) / 2); } private void calc(int idx) { values[idx] = Math.max(values[idx * 2 + 1], values[idx * 2 + 2]); if (idx > 0) { calc((idx - 1) / 2); } } public int getMax(int left, int right) { return getMax(0, 0, size, left, right); } private int getMax(int idx, int min, int max, int left, int right) { if (right <= min || max <= left) { return 0; } else if (left <= min && max <= right) { return values[idx]; } else { return Math.max(getMax(idx * 2 + 1, min, (min + max) / 2, left, right) , getMax(idx * 2 + 2, (min + max) / 2, max, left, right)); } } } } class FastScanner { private DataInputStream din; private byte[] buffer; private int bufferPointer, bytesRead; private static final int BUFFER_SIZE = 1 << 16; // 65,536 バイト public FastScanner() { din = new DataInputStream(System.in); buffer = new byte[BUFFER_SIZE]; bufferPointer = bytesRead = 0; } private byte read() { try { if (bufferPointer == bytesRead) { bytesRead = din.read(buffer, 0, BUFFER_SIZE); if (bytesRead == -1) return -1; bufferPointer = 0; } return buffer[bufferPointer++]; } catch (IOException e) { throw new RuntimeException(e); } } public String next() { byte b = read(); // 空白文字を読み飛ばす while (isSpaceChar(b)) { b = read(); } StringBuilder sb = new StringBuilder(); while (!isSpaceChar(b)) { sb.append((char) b); b = read(); } return sb.toString(); } public int nextInt() { int ret = 0; byte c = read(); while (isSpaceChar(c)) c = read(); boolean neg = (c == '-'); if (neg) c = read(); do { ret = ret * 10 + c - '0'; c = read(); } while (!isSpaceChar(c)); return neg ? -ret : ret; } public long nextLong() { long ret = 0; byte c = read(); while (isSpaceChar(c)) c = read(); boolean neg = (c == '-'); if (neg) c = read(); do { ret = ret * 10L + c - '0'; c = read(); } while (!isSpaceChar(c)); return neg ? -ret : ret; } public double nextDouble() { double ret = 0, div = 1; byte c = read(); while (isSpaceChar(c)) c = read(); boolean neg = (c == '-'); if (neg) c = read(); do { ret = ret * 10 + c - '0'; c = read(); } while (!isSpaceChar(c) && c != '.'); if (c == '.') { while (!isSpaceChar(c = read())) { ret += (c - '0') / (div *= 10); } } return neg ? -ret : ret; } private boolean isSpaceChar(byte c) { return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1; } public void close() { try { if (din != null) din.close(); } catch (IOException e) { throw new RuntimeException(e); } } }