結果
| 問題 | No.1558 Derby Live |
| ユーザー |
 cyclerecycle9
|
| 提出日時 | 2021-09-12 08:10:27 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 8,651 bytes |
| コンパイル時間 | 2,835 ms |
| コンパイル使用メモリ | 84,480 KB |
| 実行使用メモリ | 847,580 KB |
| 最終ジャッジ日時 | 2024-06-23 19:59:06 |
| 合計ジャッジ時間 | 9,262 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | MLE | - |
| testcase_01 | -- | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
ソースコード
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, 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;
static S E;
public S(int[] p){
this.p = p;
int[] e = new int[N];
Arrays.setAll(e, k -> k);
E = new S(e);
}
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で更新(一点加算なら更新でおｋ)
//二ブタンも出来る
//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)
);
}
}
}