結果
| 問題 | No.3782 Synchronized Subsequences |
| コンテスト | |
| ユーザー |
 37zigen
|
| 提出日時 | 2026-10-30 22:57:04 |
| 言語 | Java (openjdk 27 + ACL) |
| 結果 |
TLE
不安定
|
| 実行時間 | - |
| コード長 | 23,210 bytes |
| 記録 | |
| コンパイル時間 | 3,283 ms |
| コンパイル使用メモリ | 107,076 KB |
| 実行使用メモリ | 781,956 KB |
| 最終ジャッジ日時 | 2026-10-30 22:57:23 |
| 合計ジャッジ時間 | 17,790 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge7_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 20 TLE * 1 -- * 19 |
ソースコード
public class Main implements java.lang.Runnable {
static MyPrintWriter pw = MyPrintWriter.getInstance();
static FastScanner sc = FastScanner.getInstance();
public static void main(java.lang.String[] args) throws java.io.IOException {
new Main().run();
Main.pw.flush();
// JavaToCpp.export();
}
@java.lang.Override
public void run() {
int T = Main.sc.nextInt();
for (int TEST = 0; TEST < T; TEST++) {
int N = Main.sc.nextInt();
int[] P = Main.sc.nextInts(N);
int[] Q = Main.sc.nextInts(N);
ArrayUtils.decrementAll(P);
ArrayUtils.decrementAll(Q);
CompressedSparseBinaryIndexedTree3D inc = new CompressedSparseBinaryIndexedTree3D(new LongCommutativeMonoidStrategy() {
@java.lang.Override
public long mul(long a, long b) {
return java.lang.Math.max(a, b);
}
@java.lang.Override
public long identity() {
return 0;
}
});
CompressedSparseBinaryIndexedTree3D dec = new CompressedSparseBinaryIndexedTree3D(new LongCommutativeMonoidStrategy() {
@java.lang.Override
public long mul(long a, long b) {
return java.lang.Math.max(a, b);
}
@java.lang.Override
public long identity() {
return 0;
}
});
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
inc.registerKey(P[i], j, Q[j]);
dec.registerKey(N - P[i], j, N - Q[j]);
}
}
inc.build();
dec.build();
long ans = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
{
long v = inc.prefixSum(P[i], j, Q[j]) + 1;
inc.add(P[i], j, Q[j], v);
dec.add(N - P[i], j, N - Q[j], v);
ans = java.lang.Math.max(ans, v);
}
{
long v = dec.prefixSum(N - P[i], j, N - Q[j]) + 1;
inc.add(P[i], j, Q[j], v);
dec.add(N - P[i], j, N - Q[j], v);
ans = java.lang.Math.max(ans, v);
}
}
}
Main.pw.println(ans);
}
}
}
class ArrayUtils {
public static void decrementAll(int[] a) {
for (int i = 0; i < a.length; i++) {
a[i]--;
}
}
public static long[] sortq(long[] a) {
if (a.length == 0) {
return new long[0];
}
long[] b = a.clone();
java.util.Arrays.sort(b);
int pointer = 1;
for (int i = 1; i < b.length; i++) {
if (b[pointer - 1] != b[i]) {
b[pointer++] = b[i];
}
}
return java.util.Arrays.copyOf(b, pointer);
}
}
/**
* 3次元座標圧縮三次元 Binary Indexed Tree (Fenwick Tree)。
*
* 各外側・中間 BIT ノードに必要な座標だけを持たせることで、空間計算量 O(N log^2 N) を達成する。
* 点更新と長方体領域の和取得を O(log^3 N) で行う。
*
* <p>契約:</p>
* <ul>
* <li>事前条件: 使用する座標 (x, y, z) は事前に registerKey または register によって登録されている必要がある。</li>
* <li>計算量: 構築に O(N log^2 N)、一点作用・領域クエリに O(log^3 N)</li>
* </ul>
*/
// 未テスト
class CompressedSparseBinaryIndexedTree3D {
/**
* 作用させる二項演算（アーベル群または可換モノイドの演算）
*/
private final java.util.function.LongBinaryOperator op;
/**
* 逆元（可換モノイドの場合は null になることがある）
*/
private final java.util.function.LongUnaryOperator inv;
/**
* 単位元
*/
private final long identity;
/**
* 登録された一意なX座標のソート済み配列
*/
private long[] xs;
/**
* 各外側 BIT ノード (1-indexed) に対応する、登録された一意なY座標のソート済み配列
*/
private long[][] ys;
/**
* 各外側・中間 BIT ノード (1-indexed) に対応する、登録された一意なZ座標のソート済み配列
*/
private long[][][] zs;
/**
* 各外側・中間 BIT ノードにおける 1D BIT データの配列
*/
private long[][][] tree;
/**
* 構築が完了したかを表すフラグ
*/
private boolean built = false;
/**
* 事前登録されたX座標のリスト
*/
private final LongArrayList regX = new LongArrayList();
/**
* 事前登録されたY座標のリスト
*/
private final LongArrayList regY = new LongArrayList();
/**
* 事前登録されたZ座標のリスト
*/
private final LongArrayList regZ = new LongArrayList();
/**
* 標準的な加法群 (long, +, -, 0) を用いて 3次元 圧縮 BIT を構築する。
*/
public CompressedSparseBinaryIndexedTree3D() {
this(LongAddAbelianGroupStrategy.STRATEGY);
}
/**
* 可換モノイドの戦略を用いて 3次元 圧縮 BIT を構築する。
*
* @param strategy
* 可換モノイドの戦略
*/
public CompressedSparseBinaryIndexedTree3D(LongCommutativeMonoidStrategy strategy) {
this.op = strategy::mul;
this.inv = (strategy instanceof LongGroupStrategy) ? ((LongGroupStrategy) (strategy))::inverse : null;
this.identity = strategy.identity();
}
/**
* アーベル群の戦略を用いて 3次元 圧縮 BIT を構築する。
*
* @param strategy
* アーベル群の戦略
*/
public CompressedSparseBinaryIndexedTree3D(LongAbelianGroupStrategy strategy) {
this.op = strategy::mul;
this.inv = strategy::inverse;
this.identity = strategy.identity();
}
/**
* 指定された演算を用いて 3次元 圧縮 BIT を構築する。
*
* @param op
* 二項演算
* @param inv
* 逆元（逆元が存在しない場合は null）
* @param identity
* 単位元
*/
public CompressedSparseBinaryIndexedTree3D(java.util.function.LongBinaryOperator op, java.util.function.LongUnaryOperator inv, long identity) {
this.op = op;
this.inv = inv;
this.identity = identity;
}
/**
* 更新を作用させる座標 (x, y, z) を事前に登録する。
*
* <p>契約:</p>
* <ul>
* <li>計算量: O(1)</li>
* <li>破壊的変更: あり</li>
* </ul>
*
* @param x
* X座標
* @param y
* Y座標
* @param z
* Z座標
*/
// 未テスト
public void registerKey(long x, long y, long z) {
regX.add(x);
regY.add(y);
regZ.add(z);
}
/**
* 登録された座標情報に基づいて 3次元 圧縮 BIT を構築する。
*
* <p>契約:</p>
* <ul>
* <li>事前条件: 登録済みの座標が 1 つ以上存在することが望ましい。</li>
* <li>計算量: O(N log^2 N) (N は登録された座標の個数)</li>
* <li>破壊的変更: あり</li>
* </ul>
*/
// 未テスト
public void build() {
if (built) {
return;
}
long[] allX = regX.toArray();
this.xs = ArrayUtils.sortq(allX);
int H = xs.length;
LongArrayList[] tempYs = new LongArrayList[H + 1];
for (int i = 0; i <= H; i++) {
tempYs[i] = new LongArrayList();
}
int N = regX.size();
for (int p = 0; p < N; p++) {
long x = regX.get(p);
long y = regY.get(p);
int i = SortedArrays.indexOf(xs, x) + 1;
for (int idx = i; idx <= H; idx += idx & (-idx)) {
tempYs[idx].add(y);
}
}
this.ys = new long[H + 1][];
for (int idx = 1; idx <= H; idx++) {
this.ys[idx] = ArrayUtils.sortq(tempYs[idx].toArray());
}
this.zs = new long[H + 1][][];
this.tree = new long[H + 1][][];
LongArrayList[][] tempZs = new LongArrayList[H + 1][];
for (int idx = 1; idx <= H; idx++) {
int lenY = ys[idx].length;
tempZs[idx] = new LongArrayList[lenY + 1];
for (int jdx = 1; jdx <= lenY; jdx++) {
tempZs[idx][jdx] = new LongArrayList();
}
}
for (int p = 0; p < N; p++) {
long x = regX.get(p);
long y = regY.get(p);
long z = regZ.get(p);
int i = SortedArrays.indexOf(xs, x) + 1;
for (int idx = i; idx <= H; idx += idx & (-idx)) {
int j = SortedArrays.indexOf(ys[idx], y) + 1;
int lenY = ys[idx].length;
for (int jdx = j; jdx <= lenY; jdx += jdx & (-jdx)) {
tempZs[idx][jdx].add(z);
}
}
}
for (int idx = 1; idx <= H; idx++) {
int lenY = ys[idx].length;
this.zs[idx] = new long[lenY + 1][];
this.tree[idx] = new long[lenY + 1][];
for (int jdx = 1; jdx <= lenY; jdx++) {
long[] sortedZ = ArrayUtils.sortq(tempZs[idx][jdx].toArray());
this.zs[idx][jdx] = sortedZ;
this.tree[idx][jdx] = new long[sortedZ.length + 1];
if (identity != 0L) {
java.util.Arrays.fill(this.tree[idx][jdx], identity);
}
}
}
this.built = true;
}
/**
* 座標 (x, y, z) に値 val を作用させる。
*
* <p>契約:</p>
* <ul>
* <li>事前条件: 座標 (x, y, z) が事前に登録され、build() が完了していること。</li>
* <li>計算量: O(log^3 N)</li>
* <li>破壊的変更: あり</li>
* </ul>
*
* @param x
* X座標
* @param y
* Y座標
* @param z
* Z座標
* @param val
* 作用させる値
*/
// 未テスト
public void add(long x, long y, long z, long val) {
if (!built) {
throw new java.lang.AssertionError("Not built yet.");
}
int i = SortedArrays.indexOf(xs, x) + 1;
if (i == 0) {
throw new java.lang.AssertionError("x coordinate is not registered: " + x);
}
int H = xs.length;
for (int idx = i; idx <= H; idx += idx & (-idx)) {
int j = SortedArrays.indexOf(ys[idx], y) + 1;
if (j == 0) {
throw new java.lang.AssertionError((("y coordinate is not registered at outer BIT node " + idx) + ": ") + y);
}
int lenY = ys[idx].length;
for (int jdx = j; jdx <= lenY; jdx += jdx & (-jdx)) {
int k = SortedArrays.indexOf(zs[idx][jdx], z) + 1;
if (k == 0) {
throw new java.lang.AssertionError((((("z coordinate is not registered at middle BIT node " + jdx) + " under outer node ") + idx) + ": ") + z);
}
int lenZ = zs[idx][jdx].length;
for (int kdx = k; kdx <= lenZ; kdx += kdx & (-kdx)) {
tree[idx][jdx][kdx] = op.applyAsLong(tree[idx][jdx][kdx], val);
}
}
}
}
/**
* 半開区間 (-inf, x) x (-inf, y) x (-inf, z) の総和を返す。
*
* <p>契約:</p>
* <ul>
* <li>事前条件: build() が完了していること。</li>
* <li>計算量: O(log^3 N)</li>
* <li>破壊的変更: なし</li>
* </ul>
*
* @param x
* X座標の上限 (exclusive)
* @param y
* Y座標の上限 (exclusive)
* @param z
* Z座標の上限 (exclusive)
* @return 領域内の総和
*/
// 未テスト
public long prefixSum(long x, long y, long z) {
if (!built) {
throw new java.lang.AssertionError("Not built yet.");
}
long res = identity;
int i = SortedArrays.ceil(xs, x);
for (int idx = i; idx > 0; idx -= idx & (-idx)) {
int j = SortedArrays.ceil(ys[idx], y);
for (int jdx = j; jdx > 0; jdx -= jdx & (-jdx)) {
int k = SortedArrays.ceil(zs[idx][jdx], z);
for (int kdx = k; kdx > 0; kdx -= kdx & (-kdx)) {
res = op.applyAsLong(res, tree[idx][jdx][kdx]);
}
}
}
return res;
}
}
class FastScanner {
private static FastScanner instance = null;
private final java.io.InputStream in = java.lang.System.in;
private final byte[] buffer = new byte[1 << 16];
private int ptr = 0;
private int buflen = 0;
private FastScanner() {
}
public static FastScanner getInstance() {
if (FastScanner.instance == null) {
FastScanner.instance = new FastScanner();
}
return FastScanner.instance;
}
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 int readByte() {
if (hasNextByte()) {
return buffer[ptr++];
} else {
return -1;
}
}
private boolean isPrintableChar(int c) {
return (33 <= c) && (c <= 126);
}
public boolean hasNext() {
while (hasNextByte() && (!isPrintableChar(buffer[ptr]))) {
ptr++;
}
return hasNextByte();
}
public long nextLong() {
if (!hasNext()) {
throw new java.util.NoSuchElementException();
}
long n = 0;
boolean minus = false;
int b = readByte();
if (b == '-') {
minus = true;
b = readByte();
}
while ((b >= '0') && (b <= '9')) {
// n = n * 10 + (b - '0');
n = ((n << 1) + (n << 3)) + (b - '0');
b = readByte();
}
return minus ? -n : n;
}
public int nextInt() {
return ((int) (nextLong()));
}
public int[] nextInts(int n) {
int[] a = new int[n];
for (int i = 0; i < n; ++i) {
a[i] = nextInt();
}
return a;
}
}
/**
* アーベル群。
*/
interface LongAbelianGroupStrategy extends LongGroupStrategy , LongCommutativeMonoidStrategy {}
/**
* 加法アーベル群。
*/
enum LongAddAbelianGroupStrategy implements LongAbelianGroupStrategy {
STRATEGY;
@java.lang.Override
public long identity() {
return 0;
}
@java.lang.Override
public long mul(long a, long b) {
return a + b;
}
@java.lang.Override
public long inverse(long a) {
return -a;
}
@java.lang.Override
public long pow(long a, long n) {
return a * n;
}
}
/**
* *
* lenがa.lengthに比べて小さくなっても配列を取り直さない。
*/
class LongArrayList implements java.lang.Iterable<java.lang.Long> {
@java.lang.SuppressWarnings("unchecked")
long[] a;
int tail = 0;
int len = 0;
int capacity = 16;
public LongArrayList() {
a = new long[capacity];
}
public LongArrayList(int capacity) {
this.capacity = capacity;
a = new long[capacity];
}
public void add(long v) {
if (len == a.length) {
resize(2 * len);
}
a[tail] = v;
tail++;
++len;
}
public long get(int id) {
if ((id < 0) || (id >= len)) {
throw new java.lang.IndexOutOfBoundsException(((((("get(" + id) + ")は添え字") + 0) + "以上") + (len - 1)) + "以下に違反");
}
return a[id];
}
void resize(int size) {
a = java.util.Arrays.copyOf(a, size);
tail = len;
}
public int size() {
return len;
}
public long[] toArray() {
return java.util.Arrays.copyOf(a, len);
}
@java.lang.Override
public java.util.PrimitiveIterator.OfLong iterator() {
return new java.util.PrimitiveIterator.OfLong() {
int idx = 0;
@java.lang.Override
public boolean hasNext() {
return idx < len;
}
@java.lang.Override
public long nextLong() {
if (!hasNext()) {
throw new java.util.NoSuchElementException();
}
return get(idx++);
}
};
}
/**
* 内部状態を文字列として表す。
* <ul>
* <li>事前条件: 特になし。</li>
* <li>事後条件: 特になし。</li>
* <li>計算量: O(N)</li>
* <li>破壊的変更: なし。</li>
* </ul>
*
* @return 内部状態の文字列表現
*/
// 未テスト
@java.lang.Override
public java.lang.String toString() {
return ("LongArrayList { elements: " + java.util.Arrays.toString(toArray())) + " }";
}
}
/**
* 可換モノイド。
*/
interface LongCommutativeMonoidStrategy extends LongMonoidStrategy {}
interface LongGroupStrategy extends LongMonoidStrategy {
long identity();
long mul(long a, long b);
long inverse(long a);
default long pow(long a, long n) {
long ret = identity();
long c = (n < 0) ? inverse(a) : a;
if (n < 0) {
if (n == java.lang.Long.MIN_VALUE) {
ret = mul(ret, c);
n = -(n + 1);
} else {
n = -n;
}
}
while (n != 0) {
if ((n % 2) == 1) {
ret = mul(ret, c);
}
c = mul(c, c);
n /= 2;
}
return ret;
}
}
@java.lang.SuppressWarnings("hiding")
interface LongMonoidStrategy {
long identity();
long mul(long a, long b);
default long pow(long a, long n) {
if (n < 0) {
throw new java.lang.AssertionError();
}
long ret = identity();
while (n != 0) {
if ((n % 2) == 1) {
ret = mul(ret, a);
}
a = mul(a, a);
n /= 2;
}
return ret;
}
}
class MyPrintWriter extends java.io.PrintWriter {
private static MyPrintWriter instance = null;
private MyPrintWriter() {
super(java.lang.System.out);
}
public static MyPrintWriter getInstance() {
if (MyPrintWriter.instance == null) {
MyPrintWriter.instance = new MyPrintWriter();
}
return MyPrintWriter.instance;
}
public MyPrintWriter(java.io.PrintStream out) {
super(out);
}
}
class SortedArrays {
/**
* key > a[i] となる最大の i を返す。aはソートされているとする。
*
* @param a
* @param key
* @return */
public static int lower(long[] a, long key) {
int ok = -1;
int ng = a.length;
while ((ng - ok) > 1) {
int m = (ok + ng) / 2;
if (key > a[m]) {
ok = m;
} else {
ng = m;
}
}
return ok;
}
/**
* key <= a[i] となる最小の i を返す。
*
* @param a
* @param key
* @return */
public static int ceil(long[] a, long key) {
int ok = a.length;
int ng = -1;
while ((ok - ng) > 1) {
int m = (ok + ng) / 2;
if (a[m] >= key) {
ok = m;
} else {
ng = m;
}
}
return ok;
}
/**
* key = a[i] となる最小の i を返す。存在しなければ-1
* 未テスト
*
* @param a
* @param key
* @return */
public static int indexOf(long[] a, long key) {
int ret = SortedArrays.lower(a, key) + 1;
if (((0 <= ret) && (ret < a.length)) && (a[ret] == key)) {
return ret;
} else {
return -1;
}
}
}
// --- Original Code ---
// import java.io.IOException;
// import java.util.Arrays;
// import java.util.Random;
//
// import library.tools.FastScanner;
// import library.tools.MergeFiles;
// import library.tools.MyPrintWriter;
// import library.util.ArrayUtils;
// import library.util.Fp;
// import library.util.algebra.strategy.longs.LongCommutativeMonoidStrategy;
// import library.util.segtree.CompressedSparseBinaryIndexedTree3D;
//
// public class Main implements Runnable {
//
// static MyPrintWriter pw = MyPrintWriter.getInstance();
// static FastScanner sc = FastScanner.getInstance();
//
// public static void main(String[] args) throws IOException {
// new Main().run();
// pw.flush();
// MergeFiles.export();
// // JavaToCpp.export();
// }
//
// Random r = new Random();
// Fp fp = Fp.MOD998244353;
// long mod = fp.modulus();
//
// @java.lang.Override
// public void run() {
// int T=sc.nextInt();
// for (int TEST = 0; TEST < T; TEST++) {
// int N=sc.nextInt();
// int[]P=sc.nextInts(N);
// int[]Q=sc.nextInts(N);
// ArrayUtils.decrementAll(P);
// ArrayUtils.decrementAll(Q);
// CompressedSparseBinaryIndexedTree3D inc=new CompressedSparseBinaryIndexedTree3D(new LongCommutativeMonoidStrategy() {
//
// @Override
// public long mul(long a, long b) {
// return Math.max(a, b);
// }
//
// @Override
// public long identity() {
// return 0;
// }
// });
// CompressedSparseBinaryIndexedTree3D dec=new CompressedSparseBinaryIndexedTree3D(new LongCommutativeMonoidStrategy() {
//
// @Override
// public long mul(long a, long b) {
// return Math.max(a, b);
// }
//
// @Override
// public long identity() {
// return 0;
// }
// });
// for (int i = 0; i < N; i++) {
// for (int j = 0; j < N; j++) {
// inc.registerKey(P[i], j, Q[j]);
// dec.registerKey(N-P[i], j, N-Q[j]);
// }
// }
// inc.build();
// dec.build();
// long ans=0;
// for (int i = 0; i < N; i++) {
// for (int j = 0; j < N; j++) {
// {
// long v=inc.prefixSum(P[i], j, Q[j])+1;
// inc.add(P[i], j, Q[j], v);
// dec.add(N-P[i], j, N-Q[j], v);
// ans=Math.max(ans, v);
// }
// {
// long v=dec.prefixSum(N-P[i], j, N-Q[j])+1;
// inc.add(P[i], j, Q[j], v);
// dec.add(N-P[i], j, N-Q[j], v);
// ans=Math.max(ans, v);
// }
//
// }
// }
// pw.println(ans);
// }
//
// }
//
// void tr(Object... objects) {
// System.out.println(Arrays.deepToString(objects));
// }
//
// }
//
//
//
//
//