結果
問題 | No.1558 Derby Live |
ユーザー | cyclerecycle9 |
提出日時 | 2021-09-12 08:02:49 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 489 ms / 2,000 ms |
コード長 | 8,571 bytes |
コンパイル時間 | 2,454 ms |
コンパイル使用メモリ | 83,472 KB |
実行使用メモリ | 73,372 KB |
最終ジャッジ日時 | 2023-09-06 00:44:38 |
合計ジャッジ時間 | 20,518 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 314 ms
64,552 KB |
testcase_01 | AC | 489 ms
72,076 KB |
testcase_02 | AC | 51 ms
50,156 KB |
testcase_03 | AC | 388 ms
64,400 KB |
testcase_04 | AC | 247 ms
57,996 KB |
testcase_05 | AC | 239 ms
57,876 KB |
testcase_06 | AC | 340 ms
59,696 KB |
testcase_07 | AC | 122 ms
53,340 KB |
testcase_08 | AC | 323 ms
59,592 KB |
testcase_09 | AC | 337 ms
62,952 KB |
testcase_10 | AC | 331 ms
60,812 KB |
testcase_11 | AC | 363 ms
62,700 KB |
testcase_12 | AC | 363 ms
62,900 KB |
testcase_13 | AC | 375 ms
66,484 KB |
testcase_14 | AC | 386 ms
66,440 KB |
testcase_15 | AC | 405 ms
68,416 KB |
testcase_16 | AC | 422 ms
70,828 KB |
testcase_17 | AC | 423 ms
69,404 KB |
testcase_18 | AC | 438 ms
71,052 KB |
testcase_19 | AC | 447 ms
70,080 KB |
testcase_20 | AC | 481 ms
73,300 KB |
testcase_21 | AC | 441 ms
70,420 KB |
testcase_22 | AC | 470 ms
70,520 KB |
testcase_23 | AC | 477 ms
71,744 KB |
testcase_24 | AC | 453 ms
70,772 KB |
testcase_25 | AC | 470 ms
71,960 KB |
testcase_26 | AC | 475 ms
73,372 KB |
testcase_27 | AC | 453 ms
70,684 KB |
testcase_28 | AC | 471 ms
71,980 KB |
testcase_29 | AC | 476 ms
72,108 KB |
testcase_30 | AC | 443 ms
69,652 KB |
testcase_31 | AC | 461 ms
71,624 KB |
testcase_32 | AC | 474 ms
71,172 KB |
testcase_33 | AC | 74 ms
50,912 KB |
testcase_34 | AC | 73 ms
51,388 KB |
ソースコード
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.math.BigDecimal; import java.math.RoundingMode; import java.util.*; public class Main { static final long MOD1=1000000007; static final long MOD=998244353; static int ans=0; static int N; public static void main(String[] args){ PrintWriter out = new PrintWriter(System.out); InputReader sc=new InputReader(System.in); N = sc.nextInt(); int M = sc.nextInt(); int Q = sc.nextInt(); int[] e = new int[N]; for (int i = 0; i < e.length; i++) { e[i] = i; } SegTree<S> segTree = new SegTree<S>(M, S::map, new S(e)); for (int i = 0; i < Q; i++) { int x = sc.nextInt(); if (x==1) { int D = sc.nextInt(); int[] P = sc.nextIntArray(N); Arrays.setAll(P, k -> P[k]-1); segTree.set(D-1, new S(P)); }else if (x==2) { int S = sc.nextInt(); S p = segTree.prod(0, S); int[] p_inv = new int[N]; for (int j = 0; j < p_inv.length; j++) { p_inv[p.p[j]] = j; } for (int j = 0; j < N; j++){ out.print((p_inv[j]+1)+" "); } out.println(); }else { int L = sc.nextInt()-1; int R = sc.nextInt(); int ans = 0; S pl = segTree.prod(0, L); S pr = segTree.prod(0, R); for (int j = 0; j < N; j++) { ans += Math.abs(pl.p[j] - pr.p[j]); } out.println(ans); } } out.flush(); } static class S{ int[] p; public S(int[] p){ this.p = p; } static S map(S a,S b){ int[] ps = new int[N]; for (int i = 0; i < N; i++) { ps[i] = b.p[a.p[i]]; } return new S(ps); } } static class InputReader { private InputStream in; private byte[] buffer = new byte[1024]; private int curbuf; private int lenbuf; public InputReader(InputStream in) { this.in = in; this.curbuf = this.lenbuf = 0; } public boolean hasNextByte() { if (curbuf >= lenbuf) { curbuf = 0; try { lenbuf = in.read(buffer); } catch (IOException e) { throw new InputMismatchException(); } if (lenbuf <= 0) return false; } return true; } private int readByte() { if (hasNextByte()) return buffer[curbuf++]; else return -1; } private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); } private void skip() { while (hasNextByte() && isSpaceChar(buffer[curbuf])) curbuf++; } public boolean hasNext() { skip(); return hasNextByte(); } public String next() { if (!hasNext()) throw new NoSuchElementException(); StringBuilder sb = new StringBuilder(); int b = readByte(); while (!isSpaceChar(b)) { sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } public int nextInt() { if (!hasNext()) throw new NoSuchElementException(); int c = readByte(); while (isSpaceChar(c)) c = readByte(); boolean minus = false; if (c == '-') { minus = true; c = readByte(); } int res = 0; do { if (c < '0' || c > '9') throw new InputMismatchException(); res = res * 10 + c - '0'; c = readByte(); } while (!isSpaceChar(c)); return (minus) ? -res : res; } public long nextLong() { if (!hasNext()) throw new NoSuchElementException(); int c = readByte(); while (isSpaceChar(c)) c = readByte(); boolean minus = false; if (c == '-') { minus = true; c = readByte(); } long res = 0; do { if (c < '0' || c > '9') throw new InputMismatchException(); res = res * 10 + c - '0'; c = readByte(); } while (!isSpaceChar(c)); return (minus) ? -res : res; } public double nextDouble() { return Double.parseDouble(next()); } public int[] nextIntArray(int n) { int[] a = new int[n]; for (int i = 0; i < n; i++) a[i] = nextInt(); return a; } public double[] nextDoubleArray(int n) { double[] a = new double[n]; for (int i = 0; i < n; i++) a[i] = nextDouble(); return a; } public long[] nextLongArray(int n) { long[] a = new long[n]; for (int i = 0; i < n; i++) a[i] = nextLong(); return a; } public char[][] nextCharMap(int n, int m) { char[][] map = new char[n][m]; for (int i = 0; i < n; i++) map[i] = next().toCharArray(); return map; } } } //funはlamda式で定義 //prodで取得,setで更新(一点加算なら更新でおk) //二ブタンも出来る //SegTree<Integer> segTree=new SegTree<Integer>(N, (x,y)->x+y, 0);使用例 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) ); } } }