結果
問題 | No.789 範囲の合計 |
ユーザー | mikit |
提出日時 | 2020-05-31 05:40:49 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 740 ms / 1,000 ms |
コード長 | 9,199 bytes |
コンパイル時間 | 3,105 ms |
コンパイル使用メモリ | 91,912 KB |
実行使用メモリ | 97,700 KB |
最終ジャッジ日時 | 2024-04-27 17:23:37 |
合計ジャッジ時間 | 10,777 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 58 ms
51,308 KB |
testcase_01 | AC | 59 ms
50,356 KB |
testcase_02 | AC | 668 ms
86,528 KB |
testcase_03 | AC | 490 ms
58,584 KB |
testcase_04 | AC | 740 ms
97,700 KB |
testcase_05 | AC | 657 ms
93,308 KB |
testcase_06 | AC | 664 ms
86,956 KB |
testcase_07 | AC | 449 ms
57,664 KB |
testcase_08 | AC | 710 ms
95,824 KB |
testcase_09 | AC | 695 ms
97,600 KB |
testcase_10 | AC | 607 ms
78,804 KB |
testcase_11 | AC | 600 ms
87,540 KB |
testcase_12 | AC | 543 ms
88,160 KB |
testcase_13 | AC | 56 ms
50,728 KB |
testcase_14 | AC | 57 ms
50,508 KB |
ソースコード
import java.io.OutputStream; import java.io.IOException; import java.io.InputStream; import java.io.OutputStream; import java.io.PrintStream; import java.util.function.LongBinaryOperator; import java.io.IOException; import java.io.InputStreamReader; import java.util.Stack; import java.io.BufferedOutputStream; import java.io.UncheckedIOException; import java.util.Vector; import java.nio.charset.Charset; import java.util.StringTokenizer; import java.io.Writer; import java.io.OutputStreamWriter; import java.io.BufferedReader; import java.io.InputStream; /** * Built using CHelper plug-in * Actual solution is at the top * * @author mikit */ public class Main { public static void main(String[] args) { InputStream inputStream = System.in; OutputStream outputStream = System.out; LightScanner in = new LightScanner(inputStream); LightWriter out = new LightWriter(outputStream); No789 solver = new No789(); solver.solve(1, in, out); out.close(); } static class No789 { public void solve(int testNumber, LightScanner in, LightWriter out) { IntDynamicSegmentTree st = new IntDynamicSegmentTree(1 << 30, Long::sum, 0, Long::sum); int n = in.ints(); long ans = 0; for (int i = 0; i < n; i++) { if (in.ints() == 0) st.update(in.ints(), in.ints()); else ans += st.query(in.ints(), in.ints() + 1); } out.ans(ans).ln(); } } static class LightWriter implements AutoCloseable { private final Writer out; private boolean autoflush = false; private boolean breaked = true; public LightWriter(Writer out) { this.out = out; } public LightWriter(OutputStream out) { this(new OutputStreamWriter(new BufferedOutputStream(out), Charset.defaultCharset())); } public LightWriter print(char c) { try { out.write(c); breaked = false; } catch (IOException ex) { throw new UncheckedIOException(ex); } return this; } public LightWriter print(String s) { try { out.write(s, 0, s.length()); breaked = false; } catch (IOException ex) { throw new UncheckedIOException(ex); } return this; } public LightWriter ans(String s) { if (!breaked) { print(' '); } return print(s); } public LightWriter ans(long l) { return ans(Long.toString(l)); } public LightWriter ln() { print(System.lineSeparator()); breaked = true; if (autoflush) { try { out.flush(); } catch (IOException ex) { throw new UncheckedIOException(ex); } } return this; } public void close() { try { out.close(); } catch (IOException ex) { throw new UncheckedIOException(ex); } } } static class LightScanner implements AutoCloseable { private BufferedReader reader = null; private StringTokenizer tokenizer = null; public LightScanner(InputStream in) { reader = new BufferedReader(new InputStreamReader(in)); } public String string() { if (tokenizer == null || !tokenizer.hasMoreTokens()) { try { tokenizer = new StringTokenizer(reader.readLine()); } catch (IOException e) { throw new UncheckedIOException(e); } } return tokenizer.nextToken(); } public int ints() { return Integer.parseInt(string()); } public void close() { try { this.reader.close(); } catch (IOException ex) { throw new UncheckedIOException(ex); } } } static class IntDynamicSegmentTree { private final long lb; private final long ub; private Node root; private final LongBinaryOperator op; private final LongBinaryOperator up; private final long zero; private final Stack<Node> reusableStack = new Stack<>(); public IntDynamicSegmentTree(long lb, long ub, LongBinaryOperator op, long zero, LongBinaryOperator up) { if (lb > ub) throw new IllegalArgumentException(); this.lb = lb; this.ub = ub; this.root = new Node(zero); this.op = op; this.up = up; this.zero = zero; } public IntDynamicSegmentTree(long n, LongBinaryOperator op, long zero, LongBinaryOperator up) { this(0, n == 1 ? 1 : Long.highestOneBit(n - 1) << 1, op, zero, up); } public IntDynamicSegmentTree(LongBinaryOperator op, long zero, LongBinaryOperator up) { this(Long.MAX_VALUE, op, zero, up); } public void update(long i, long x) { if (i < lb || ub <= i) throw new IndexOutOfBoundsException(); Stack<Node> update = reusableStack; Node node = root; long lo = lb, hi = ub; while (hi - lo > 1) { update.push(node); long mid = (lo + hi) >> 1; if (i < mid) { if (node.l == null) node.l = new Node(zero); node = node.l; hi = mid; } else { if (node.r == null) node.r = new Node(zero); node = node.r; lo = mid; } } node.v = up.applyAsLong(node.v, x); while (!update.isEmpty()) update.pop().recalculate(); } public long query(long l, long r) { if (l < lb || ub < r || l > r) throw new IndexOutOfBoundsException(); Node node = root; long lo = lb, hi = ub, mid = (lb + ub) >> 1; while (node != null && (r < mid || mid < l)) { if (r < mid) { node = node.l; hi = mid; mid = (lo + hi) >> 1; } else { node = node.r; lo = mid; mid = (lo + hi) >> 1; } } //System.out.println("Queried on ["+l+", "+r+"), Focused on [" + lo + ", " + mid + ", " + hi + ")"); if (node == null) return zero; if (l == lo && hi == r) return node.v; return op.applyAsLong(queryL(l, node.l, lo, mid), queryR(r, node.r, mid, hi)); } private long queryL(long l, Node node, long lo, long hi) { if (lo == l) return node == null ? zero : node.v; long res = zero; while (node != null && l < hi) { long mid = (lo + hi) >> 1; if (mid < l) { lo = mid; node = node.r; } else { if (node.r != null) res = op.applyAsLong(node.r.v, res); node = node.l; hi = mid; } } return res; } private long queryR(long r, Node node, long lo, long hi) { if (r == hi) return node == null ? zero : node.v; long res = zero; while (node != null && lo < r) { long mid = (lo + hi) >> 1; if (r < mid) { hi = mid; node = node.l; } else { if (node.l != null) res = op.applyAsLong(node.l.v, res); node = node.r; lo = mid; } } return res; } public String toString() { System.out.println("Segment Tree [" + lb + ", " + ub + ")"); return root.toString(lb, ub); } private static String indent(String s, String indent) { s = s.replace("\n", "\n" + indent); return indent + s.substring(0, s.length() - indent.length()); } private class Node { Node l; Node r; long v; Node(long v) { this.v = v; } void recalculate() { if (l == null && r == null) return; if (l == null) this.v = r.v; else if (r == null) this.v = l.v; else this.v = op.applyAsLong(l.v, r.v); } public String toString(long lo, long hi) { long mid = (lo + hi) >> 1; return String.format("Node[%d, %d) = %d\n%s%s", lo, hi, v, indent(l == null ? "*\n" : l.toString(lo, mid), " "), indent(r == null ? "*\n" : r.toString(mid, hi), " ")); } } } }