結果
問題 | No.789 範囲の合計 |
ユーザー | mikit |
提出日時 | 2020-05-31 14:05:07 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 544 ms / 1,000 ms |
コード長 | 8,224 bytes |
コンパイル時間 | 2,856 ms |
コンパイル使用メモリ | 84,140 KB |
実行使用メモリ | 107,332 KB |
最終ジャッジ日時 | 2024-04-28 17:05:36 |
合計ジャッジ時間 | 9,990 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 111 ms
86,136 KB |
testcase_01 | AC | 110 ms
86,396 KB |
testcase_02 | AC | 527 ms
107,124 KB |
testcase_03 | AC | 401 ms
107,188 KB |
testcase_04 | AC | 544 ms
107,332 KB |
testcase_05 | AC | 498 ms
107,132 KB |
testcase_06 | AC | 507 ms
107,092 KB |
testcase_07 | AC | 391 ms
107,056 KB |
testcase_08 | AC | 500 ms
107,108 KB |
testcase_09 | AC | 483 ms
107,164 KB |
testcase_10 | AC | 527 ms
107,252 KB |
testcase_11 | AC | 437 ms
106,892 KB |
testcase_12 | AC | 435 ms
106,980 KB |
testcase_13 | AC | 111 ms
85,996 KB |
testcase_14 | AC | 110 ms
86,136 KB |
ソースコード
import java.io.OutputStream; import java.io.IOException; import java.io.InputStream; import java.io.OutputStream; import java.util.Arrays; import java.util.function.LongBinaryOperator; import java.io.IOException; import java.io.InputStreamReader; import java.io.BufferedOutputStream; import java.io.UncheckedIOException; 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, 100000, 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.queryRec(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 IntDynamicSegmentTree { private final long lb; private final long ub; private final LongBinaryOperator op; private final LongBinaryOperator up; private final long zero; private int used; private int allocated; private int[] l; private int[] r; private long[] v; public IntDynamicSegmentTree(long lb, long ub, int cap, LongBinaryOperator op, long zero, LongBinaryOperator up) { if (lb > ub) throw new IllegalArgumentException(); this.lb = lb; this.ub = ub; this.op = op; this.up = up; this.zero = zero; this.used = 1; int height = 64 - Long.numberOfLeadingZeros(ub - lb - 1); this.allocated = Math.max(cap * height, 1); this.l = new int[allocated]; this.r = new int[allocated]; this.v = new long[allocated]; l[0] = r[0] = -1; v[0] = zero; } public IntDynamicSegmentTree(long n, int cap, LongBinaryOperator op, long zero, LongBinaryOperator up) { this(0, n == 1 ? 1 : Long.highestOneBit(n - 1) << 1, cap, op, zero, up); } public IntDynamicSegmentTree(long n, LongBinaryOperator op, long zero, LongBinaryOperator up) { this(n, 128, op, zero, up); } public IntDynamicSegmentTree(LongBinaryOperator op, long zero, LongBinaryOperator up) { this(Integer.MAX_VALUE, op, zero, up); } private int l(int i) { return i == -1 ? -1 : l[i]; } private int r(int i) { return i == -1 ? -1 : r[i]; } private long v(int i) { return i == -1 ? zero : v[i]; } private void propagate(int i) { this.v[i] = op.applyAsLong(v(l(i)), v(r(i))); } private int createNode(long x) { if (used == allocated) { allocated <<= 1; l = Arrays.copyOf(l, allocated); r = Arrays.copyOf(r, allocated); v = Arrays.copyOf(v, allocated); } this.l[used] = this.r[used] = -1; this.v[used] = x; return used++; } private int update(long i, long x, int node, long lo, long hi) { if (node == -1) node = createNode(zero); if (hi - lo == 1) { v[node] = up.applyAsLong(v[node], x); return node; } else { long mid = (lo + hi) >> 1; if (i < mid) { l[node] = update(i, x, l[node], lo, mid); } else { r[node] = update(i, x, r[node], mid, hi); } propagate(node); } return node; } public void update(long i, long x) { update(i, x, 0, lb, ub); } private long queryRec(long l, long r, int node, long lo, long hi) { if (l <= lo && hi <= r) return v(node); if (r <= lo || hi <= l || node == -1) return zero; long mid = (lo + hi) >> 1; return op.applyAsLong(queryRec(l, r, l(node), lo, mid), queryRec(l, r, r(node), mid, hi)); } public long queryRec(long l, long r) { if (l < lb || ub < r || l > r) throw new IndexOutOfBoundsException(); return queryRec(l, r, 0, lb, ub); } public String toString() { return "IntDynamicSegmentTree(" + "range = [" + lb + ", " + ub + "), zero = " + zero + ", used " + used + " / " + allocated + ")\nl = " + Arrays.toString(Arrays.copyOf(l, used)) + "\nr = " + Arrays.toString(Arrays.copyOf(r, used)) + "\nv = " + Arrays.toString(Arrays.copyOf(v, used)) + '\n'; } } 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); } } } }