結果
問題 | No.2101 [Cherry Alpha N] ずっとこの数列だったらいいのに |
ユーザー |
![]() |
提出日時 | 2022-10-14 23:42:51 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 3,097 ms / 6,000 ms |
コード長 | 16,044 bytes |
コンパイル時間 | 4,039 ms |
コンパイル使用メモリ | 95,044 KB |
実行使用メモリ | 152,736 KB |
最終ジャッジ日時 | 2024-06-26 17:43:42 |
合計ジャッジ時間 | 94,973 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 61 ms
37,308 KB |
testcase_01 | AC | 58 ms
37,580 KB |
testcase_02 | AC | 65 ms
37,472 KB |
testcase_03 | AC | 1,820 ms
113,620 KB |
testcase_04 | AC | 2,108 ms
125,236 KB |
testcase_05 | AC | 1,388 ms
95,236 KB |
testcase_06 | AC | 2,045 ms
123,052 KB |
testcase_07 | AC | 2,340 ms
124,708 KB |
testcase_08 | AC | 2,021 ms
123,148 KB |
testcase_09 | AC | 1,342 ms
92,136 KB |
testcase_10 | AC | 1,150 ms
87,596 KB |
testcase_11 | AC | 1,659 ms
102,900 KB |
testcase_12 | AC | 2,215 ms
115,672 KB |
testcase_13 | AC | 1,227 ms
89,300 KB |
testcase_14 | AC | 954 ms
67,232 KB |
testcase_15 | AC | 2,580 ms
131,228 KB |
testcase_16 | AC | 2,185 ms
131,036 KB |
testcase_17 | AC | 782 ms
65,404 KB |
testcase_18 | AC | 2,596 ms
132,472 KB |
testcase_19 | AC | 2,787 ms
136,848 KB |
testcase_20 | AC | 2,783 ms
136,068 KB |
testcase_21 | AC | 2,756 ms
132,788 KB |
testcase_22 | AC | 2,557 ms
132,696 KB |
testcase_23 | AC | 2,587 ms
132,116 KB |
testcase_24 | AC | 2,586 ms
132,704 KB |
testcase_25 | AC | 2,620 ms
132,512 KB |
testcase_26 | AC | 2,596 ms
132,788 KB |
testcase_27 | AC | 2,753 ms
135,468 KB |
testcase_28 | AC | 2,792 ms
132,548 KB |
testcase_29 | AC | 2,472 ms
131,324 KB |
testcase_30 | AC | 2,883 ms
136,768 KB |
testcase_31 | AC | 2,565 ms
132,492 KB |
testcase_32 | AC | 2,791 ms
132,844 KB |
testcase_33 | AC | 2,328 ms
133,908 KB |
testcase_34 | AC | 2,631 ms
134,132 KB |
testcase_35 | AC | 2,896 ms
148,840 KB |
testcase_36 | AC | 3,097 ms
152,676 KB |
testcase_37 | AC | 2,843 ms
152,736 KB |
testcase_38 | AC | 587 ms
62,584 KB |
testcase_39 | AC | 910 ms
70,504 KB |
testcase_40 | AC | 1,649 ms
139,584 KB |
testcase_41 | AC | 59 ms
37,280 KB |
ソースコード
import java.util.PriorityQueue; public class Main { public static void main(String[] args) { new Main(); } public Main() { FastScanner fs = new FastScanner(); java.io.PrintWriter out = new java.io.PrintWriter(System.out); solve(fs, out); out.flush(); } public void solve(FastScanner fs, java.io.PrintWriter out) { int N = fs.nextInt(); SegTree<Long> value = new SegTree<>(N, (l, r) -> l + r, 0L); SegTree<Data> dec = new SegTree<>(N, Data::merge, new Data()); PriorityQueue<Event> event = new PriorityQueue<>(); for (int i = 0;i < N;++ i) { long A = fs.nextLong(), T = fs.nextLong(); value.set(i, A); if (A != 0) { event.add(new Event(i, T, -1)); event.add(new Event(i, T + A, 1)); } } int Q = fs.nextInt(); long[] ans = new long[Q]; PriorityQueue<Query> query = new PriorityQueue<>(); for (int i = 0;i < Q;++ i) { query.add(new Query(i, fs.nextLong(), fs.nextInt(), fs.nextInt())); } while(!query.isEmpty()) { Query que = query.poll(); while(!event.isEmpty() && event.peek().T <= que.D) { Event e = event.poll(); if (e.value == -1) { dec.set(e.index, new Data(e.T - 1)); } else { dec.set(e.index, new Data()); value.set(e.index, 0L); } } Data prod = dec.prod(que.L, que.R); ans[que.index] = value.prod(que.L, que.R) - (que.D * prod.count - prod.day); } for (int i = 0;i < Q;++ i) out.println(ans[i]); } static class Data { final long day; final int count; Data() { day = 0; count = 0; } Data(long day) { this.day = day; count = 1; } Data(Data l, Data r) { day = l.day + r.day; count = l.count + r.count; } static Data merge(Data l, Data r) { return new Data(l, r); } } class Event implements Comparable<Event>{ int index; long T, value; Event(int index, long T, long value) { this.index = index; this.T = T; this.value = value; } @Override public int compareTo(Event o) { return Long.compare(T, o.T); } } class Query implements Comparable<Query>{ int index, L, R; long D; Query(int index, long D, int L, int R) { this.index = index; this.D = D; this.L = L - 1; this.R = R; } @Override public int compareTo(Query o) { return Long.compare(D, o.D); } } /** * @verified https://atcoder.jp/contests/practice2/tasks/practice2_j */ static class SegTree<S> { final int MAX; final int N; final java.util.function.BinaryOperator<S> op; final S E; final S[] data; @SuppressWarnings("unchecked") public SegTree(int n, java.util.function.BinaryOperator<S> op, S e) { this.MAX = n; int k = 1; while (k < n) k <<= 1; this.N = k; this.E = e; this.op = op; this.data = (S[]) new Object[N << 1]; java.util.Arrays.fill(data, E); } public SegTree(S[] dat, java.util.function.BinaryOperator<S> op, S e) { this(dat.length, op, e); build(dat); } private void build(S[] dat) { int l = dat.length; System.arraycopy(dat, 0, data, N, l); for (int i = N - 1; i > 0; i--) { data[i] = op.apply(data[i << 1 | 0], data[i << 1 | 1]); } } public void set(int p, S x) { exclusiveRangeCheck(p); data[p += N] = x; p >>= 1; while (p > 0) { data[p] = op.apply(data[p << 1 | 0], data[p << 1 | 1]); p >>= 1; } } public S get(int p) { exclusiveRangeCheck(p); return data[p + N]; } public S prod(int l, int r) { if (l > r) { throw new IllegalArgumentException( String.format("Invalid range: [%d, %d)", l, r) ); } inclusiveRangeCheck(l); inclusiveRangeCheck(r); S sumLeft = E; S sumRight = E; l += N; r += N; while (l < r) { if ((l & 1) == 1) sumLeft = op.apply(sumLeft, data[l++]); if ((r & 1) == 1) sumRight = op.apply(data[--r], sumRight); l >>= 1; r >>= 1; } return op.apply(sumLeft, sumRight); } public S allProd() { return data[1]; } public int maxRight(int l, java.util.function.Predicate<S> f) { inclusiveRangeCheck(l); if (!f.test(E)) { throw new IllegalArgumentException("Identity element must satisfy the condition."); } if (l == MAX) return MAX; l += N; S sum = E; do { l >>= Integer.numberOfTrailingZeros(l); if (!f.test(op.apply(sum, data[l]))) { while (l < N) { l = l << 1; if (f.test(op.apply(sum, data[l]))) { sum = op.apply(sum, data[l]); l++; } } return l - N; } sum = op.apply(sum, data[l]); l++; } while ((l & -l) != l); return MAX; } public int minLeft(int r, java.util.function.Predicate<S> f) { inclusiveRangeCheck(r); if (!f.test(E)) { throw new IllegalArgumentException("Identity element must satisfy the condition."); } if (r == 0) return 0; r += N; S sum = E; do { r--; while (r > 1 && (r & 1) == 1) r >>= 1; if (!f.test(op.apply(data[r], sum))) { while (r < N) { r = r << 1 | 1; if (f.test(op.apply(data[r], sum))) { sum = op.apply(data[r], sum); r--; } } return r + 1 - N; } sum = op.apply(data[r], sum); } while ((r & -r) != r); return 0; } private void exclusiveRangeCheck(int p) { if (p < 0 || p >= MAX) { throw new IndexOutOfBoundsException( String.format("Index %d out of bounds for the range [%d, %d).", p, 0, MAX) ); } } private void inclusiveRangeCheck(int p) { if (p < 0 || p > MAX) { throw new IndexOutOfBoundsException( String.format("Index %d out of bounds for the range [%d, %d].", p, 0, MAX) ); } } // **************** DEBUG **************** // private int indent = 6; public void setIndent(int newIndent) { this.indent = newIndent; } @Override public String toString() { return toSimpleString(); } public String toDetailedString() { return toDetailedString(1, 0); } private String toDetailedString(int k, int sp) { if (k >= N) return indent(sp) + data[k]; String s = ""; s += toDetailedString(k << 1 | 1, sp + indent); s += "\n"; s += indent(sp) + data[k]; s += "\n"; s += toDetailedString(k << 1 | 0, sp + indent); return s; } private static String indent(int n) { StringBuilder sb = new StringBuilder(); while (n --> 0) sb.append(' '); return sb.toString(); } public String toSimpleString() { StringBuilder sb = new StringBuilder(); sb.append('['); for (int i = 0; i < N; i++) { sb.append(data[i + N]); if (i < N - 1) sb.append(',').append(' '); } sb.append(']'); return sb.toString(); } } final int MOD = 998_244_353; int plus(int n, int m) { int sum = n + m; if (sum >= MOD) sum -= MOD; return sum; } int minus(int n, int m) { int sum = n - m; if (sum < 0) sum += MOD; return sum; } int times(int n, int m) { return (int)((long)n * m % MOD); } int divide(int n, int m) { return times(n, IntMath.pow(m, MOD - 2, MOD)); } int[] fact, invf; void calc(int len) { len += 2; fact = new int[len]; invf = new int[len]; fact[0] = fact[1] = invf[0] = invf[1] = 1; for (int i = 2;i < fact.length;++ i) fact[i] = times(fact[i - 1], i); invf[len - 1] = divide(1, fact[len - 1]); for (int i = len - 1;i > 1;-- i) invf[i - 1] = times(i, invf[i]); } int comb(int n, int m) { if (n < m) return 0; return times(fact[n], times(invf[n - m], invf[m])); } } class FastScanner { private final java.io.InputStream in = System.in; private final byte[] buffer = new byte[8192]; private int ptr = 0; private int buflen = 0; private boolean hasNextByte() { if (ptr < buflen) return true; ptr = 0; try { buflen = in.read(buffer); } catch (java.io.IOException e) { e.printStackTrace(); } return buflen > 0; } private byte readByte() { return hasNextByte() ? buffer[ptr++ ] : -1; } private static boolean isPrintableChar(byte c) { return 32 < c || c < 0; } private static boolean isNumber(int c) { return '0' <= c && c <= '9'; } public boolean hasNext() { while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++ ; return hasNextByte(); } public String next() { if (!hasNext()) throw new java.util.NoSuchElementException(); StringBuilder sb = new StringBuilder(); byte b; while (isPrintableChar(b = readByte())) sb.appendCodePoint(b); return sb.toString(); } public final char nextChar() { if (!hasNext()) throw new java.util.NoSuchElementException(); return (char)readByte(); } public final long nextLong() { if (!hasNext()) throw new java.util.NoSuchElementException(); long n = 0; try { byte b = readByte(); if (b == '-') { while (isNumber(b = readByte())) n = n * 10 + '0' - b; return n; } else if (!isNumber(b)) throw new NumberFormatException(); do n = n * 10 + b - '0'; while (isNumber(b = readByte())); } catch (java.util.NoSuchElementException e) {} return n; } public final int nextInt() { if (!hasNext()) throw new java.util.NoSuchElementException(); int n = 0; try { byte b = readByte(); if (b == '-') { while (isNumber(b = readByte())) n = n * 10 + '0' - b; return n; } else if (!isNumber(b)) throw new NumberFormatException(); do n = n * 10 + b - '0'; while (isNumber(b = readByte())); } catch (java.util.NoSuchElementException e) {} return n; } public double nextDouble() { return Double.parseDouble(next()); } } class Arrays { public static void sort(final int[] array) { sort(array, 0, array.length); } public static void sort(final int[] array, int fromIndex, int toIndex) { if (toIndex - fromIndex <= 512) { java.util.Arrays.sort(array, fromIndex, toIndex); return; } sort(array, fromIndex, toIndex, 0, new int[array.length]); } private static final void sort(int[] a, final int from, final int to, final int l, final int[] bucket) { if (to - from <= 512) { java.util.Arrays.sort(a, from, to); return; } final int BUCKET_SIZE = 256; final int INT_RECURSION = 4; final int MASK = 0xff; final int shift = l << 3; final int[] cnt = new int[BUCKET_SIZE + 1]; final int[] put = new int[BUCKET_SIZE]; for (int i = from; i < to; i++) ++ cnt[(a[i] >>> shift & MASK) + 1]; for (int i = 0; i < BUCKET_SIZE; i++) cnt[i + 1] += cnt[i]; for (int i = from; i < to; i++) { int bi = a[i] >>> shift & MASK; bucket[cnt[bi] + put[bi]++] = a[i]; } for (int i = BUCKET_SIZE - 1, idx = from; i >= 0; i--) { int begin = cnt[i]; int len = cnt[i + 1] - begin; System.arraycopy(bucket, begin, a, idx, len); idx += len; } final int nxtL = l + 1; if (nxtL < INT_RECURSION) { sort(a, from, to, nxtL, bucket); if (l == 0) { int lft, rgt; lft = from - 1; rgt = to; while (rgt - lft > 1) { int mid = lft + rgt >> 1; if (a[mid] < 0) lft = mid; else rgt = mid; } reverse(a, from, rgt); reverse(a, rgt, to); } } } public static void sort(final long[] array) { sort(array, 0, array.length); } public static void sort(final long[] array, int fromIndex, int toIndex) { if (toIndex - fromIndex <= 512) { java.util.Arrays.sort(array, fromIndex, toIndex); return; } sort(array, fromIndex, toIndex, 0, new long[array.length]); } private static final void sort(long[] a, final int from, final int to, final int l, final long[] bucket) { final int BUCKET_SIZE = 256; final int LONG_RECURSION = 8; final int MASK = 0xff; final int shift = l << 3; final int[] cnt = new int[BUCKET_SIZE + 1]; final int[] put = new int[BUCKET_SIZE]; for (int i = from; i < to; i++) ++ cnt[(int) ((a[i] >>> shift & MASK) + 1)]; for (int i = 0; i < BUCKET_SIZE; i++) cnt[i + 1] += cnt[i]; for (int i = from; i < to; i++) { int bi = (int) (a[i] >>> shift & MASK); bucket[cnt[bi] + put[bi]++] = a[i]; } for (int i = BUCKET_SIZE - 1, idx = from; i >= 0; i--) { int begin = cnt[i]; int len = cnt[i + 1] - begin; System.arraycopy(bucket, begin, a, idx, len); idx += len; } final int nxtL = l + 1; if (nxtL < LONG_RECURSION) { sort(a, from, to, nxtL, bucket); if (l == 0) { int lft, rgt; lft = from - 1; rgt = to; while (rgt - lft > 1) { int mid = lft + rgt >> 1; if (a[mid] < 0) lft = mid; else rgt = mid; } reverse(a, from, rgt); reverse(a, rgt, to); } } } public static void reverse(int[] array) { reverse(array, 0, array.length); } public static void reverse(int[] array, int fromIndex, int toIndex) { for (-- toIndex;fromIndex < toIndex;++ fromIndex, -- toIndex) { int swap = array[fromIndex]; array[fromIndex] = array[toIndex]; array[toIndex] = swap; } } public static void reverse(long[] array) { reverse(array, 0, array.length); } public static void reverse(long[] array, int fromIndex, int toIndex) { for (-- toIndex;fromIndex < toIndex;++ fromIndex, -- toIndex) { long swap = array[fromIndex]; array[fromIndex] = array[toIndex]; array[toIndex] = swap; } } public static void shuffle(int[] array) { java.util.Random rnd = new java.util.Random(); for (int i = 0;i < array.length;++ i) { int j = rnd.nextInt(array.length - i) + i; int swap = array[i]; array[i] = array[j]; array[j] = swap; } } public static void shuffle(long[] array) { java.util.Random rnd = new java.util.Random(); for (int i = 0;i < array.length;++ i) { int j = rnd.nextInt(array.length - i) + i; long swap = array[i]; array[i] = array[j]; array[j] = swap; } } } class IntMath { public static int gcd(int a, int b) { while (a != 0) if ((b %= a) != 0) a %= b; else return a; return b; } public static int gcd(int... array) { int ret = array[0]; for (int i = 1; i < array.length; ++i) ret = gcd(ret, array[i]); return ret; } public static long gcd(long a, long b) { while (a != 0) if ((b %= a) != 0) a %= b; else return a; return b; } public static long gcd(long... array) { long ret = array[0]; for (int i = 1; i < array.length; ++i) ret = gcd(ret, array[i]); return ret; } public static long lcm(long a, long b) { return a / gcd(a, b) * b; } public static int pow(int a, int b) { int ans = 1; for (int mul = a; b > 0; b >>= 1, mul *= mul) if ((b & 1) != 0) ans *= mul; return ans; } public static long pow(long a, long b) { long ans = 1; for (long mul = a; b > 0; b >>= 1, mul *= mul) if ((b & 1) != 0) ans *= mul; return ans; } public static int pow(int a, long b, int mod) { if (b < 0) b = b % (mod - 1) + mod - 1; long ans = 1; for (long mul = a; b > 0; b >>= 1, mul = mul * mul % mod) if ((b & 1) != 0) ans = ans * mul % mod; return (int)ans; } public static int pow(long a, long b, int mod) { return pow((int)(a % mod), b, mod); } public static int floorsqrt(long n) { return (int)Math.sqrt(n + 0.1); } public static int ceilsqrt(long n) { return n <= 1 ? (int)n : (int)Math.sqrt(n - 0.1) + 1; } }