結果
| 問題 | No.3782 Synchronized Subsequences |
| コンテスト | |
| ユーザー |
 37zigen
|
| 提出日時 | 2026-10-31 19:39:46 |
| 言語 | Java (openjdk 27.0.1.0.3 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 862 ms / 3,000 ms |
| + 590µs | |
| コード長 | 12,947 bytes |
| 記録 | |
| コンパイル時間 | 3,147 ms |
| コンパイル使用メモリ | 102,020 KB |
| 実行使用メモリ | 127,956 KB |
| 最終ジャッジ日時 | 2026-10-31 19:40:48 |
| 合計ジャッジ時間 | 23,302 ms |
|
ジャッジサーバーID （参考情報） |
judge1_0 / judge2_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 40 |
ソースコード
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);
// dp[i][j] = max(1 + dp[k][l] : k < i, P[k] < P[i], l < j, Q[l] < Q[j])
// = max(1 + f[k][j] : k < i, P[k] < P[i])
// f[i][j] = max(dp[i][l] : l < j, Q[l] < Q[j])
long[][] dp = new long[N][N];
MaxSeg[] fmax = new MaxSeg[N];
MaxSeg[] gmax = new MaxSeg[N];
for (int i = 0; i < N; i++) {
fmax[i] = new MaxSeg(N);
gmax[i] = new MaxSeg(N);
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
dp[i][j] = java.lang.Math.max(dp[i][j], 1 + java.lang.Math.max(0, fmax[j].fold(0, P[i])));
dp[i][j] = java.lang.Math.max(dp[i][j], 1 + java.lang.Math.max(0, gmax[j].fold(P[i] + 1, N)));
}
{
// f[i][*]を更新
var seg = SegTreeFactory.max(N);
for (int j = 0; j < N; j++) {
long fij = seg.fold(0, Q[j]);
seg.set(Q[j], dp[i][j]);
fmax[j].mul(P[i], fij);
}
}
{
// g[i][*]を更新
var seg = SegTreeFactory.max(N);
for (int j = 0; j < N; j++) {
long gij = seg.fold(Q[j] + 1, N);
seg.set(Q[j], dp[i][j]);
gmax[j].mul(P[i], gij);
}
}
}
Main.pw.println(ArrayUtils.max(dp));
}
}
}
class ArrayUtils {
public static void decrementAll(int[] a) {
for (int i = 0; i < a.length; i++) {
a[i]--;
}
}
public static long max(long[] a) {
long ret = java.lang.Long.MIN_VALUE;
for (int i = 0; i < a.length; ++i) {
ret = java.lang.Math.max(ret, a[i]);
}
return ret;
}
public static long max(long[][] a) {
long ret = java.lang.Long.MIN_VALUE;
for (int i = 0; i < a.length; ++i) {
ret = java.lang.Math.max(ret, ArrayUtils.max(a[i]));
}
return ret;
}
}
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;
}
}
@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 MaxSeg extends SegTreelong {
// https://atcoder.jp/contests/abc234/submissions/74021821
public MaxSeg(int n) {
super(n, java.lang.Long::max, java.lang.Long.MIN_VALUE / 3);
}
/**
* 内部状態を標準出力に出力する。
* <ul>
* <li>事前条件: 特になし。</li>
* <li>事後条件: 特になし。</li>
* <li>副作用: 標準出力への出力。</li>
* <li>計算量: O(N)</li>
* <li>破壊的変更: なし。</li>
* </ul>
*/
// 未テスト
@java.lang.Override
public void dump() {
java.lang.System.out.print("MaxSeg: ");
super.dump();
}
}
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);
}
}
/**
* null は identity の代わり
*/
class SegTreeFactory {
public static MaxSeg max(int n) {
return new MaxSeg(n);
}
}
class SegTreelong {
int n;// 2冪
int inputN;
public long[] v;
private long identity;
private java.util.function.LongBinaryOperator op;
public SegTreelong(int n, java.util.function.LongBinaryOperator op, long identiy) {
this.n = java.lang.Integer.highestOneBit(n);
if (this.n != n) {
this.n *= 2;
}
this.inputN = n;
v = new long[2 * this.n];
this.identity = identiy;
for (int i = 0; i < v.length; ++i) {
v[i] = identity;
}
this.setOp(op);
}
/**
* モノイド戦略 {@code strategy} を用いて長さ {@code n} のセグメント木を構築する。
*
* <p>計算量: O(n)</p>
* // 未テスト
*
* @param n
* 要素数
* @param strategy
* モノイドの演算および単位元を定義する Strategy
*/
public SegTreelong(int n, LongMonoidStrategy strategy) {
this(n, strategy::mul, strategy.identity());
}
/**
* モノイド戦略 {@code strategy} と初期配列 {@code a} を用いてセグメント木を構築する。
*
* <p>計算量: O(n)</p>
* // 未テスト
*
* @param a
* 初期要素配列
* @param strategy
* モノイドの演算および単位元を定義する Strategy
*/
public SegTreelong(long[] a, LongMonoidStrategy strategy) {
this(a.length, strategy);
build(a);
}
/**
* 二項演算 {@code op}、単位元 {@code identity}、初期配列 {@code a} を用いてセグメント木を構築する。
*
* <p>計算量: O(n)</p>
* // 未テスト
*
* @param a
* 初期要素配列
* @param op
* 2項演算
* @param identity
* 単位元
*/
public SegTreelong(long[] a, java.util.function.LongBinaryOperator op, long identity) {
this(a.length, op, identity);
build(a);
}
public void build(long[] a) {
for (int i = 0; i < a.length; i++) {
v[id(i, i + 1)] = a[i];
}
for (int i = n - 1; i >= 1; i--) {
v[i] = getOp().applyAsLong(v[2 * i], v[(2 * i) + 1]);
}
}
public void set(int k, long t) {
k = id(k, k + 1);
v[k] = t;
while (k != id(0, n)) {
k /= 2;
v[k] = getOp().applyAsLong(v[2 * k], v[(2 * k) + 1]);
}
}
public void mul(int k, long t) {
set(k, getOp().applyAsLong(v[id(k, k + 1)], t));
}
// [a2^k, (a+1)2^k)
int id(int a, int b) {
int w = b - a;
return (n / w) + (a / w);
}
public long fold(int l, int r) {
r = java.lang.Math.min(r, n);
l = java.lang.Math.max(l, 0);
if ((r - l) <= 0) {
return identity;
}
int ml = l + java.lang.Integer.lowestOneBit(l);
int mr = r - java.lang.Integer.lowestOneBit(r);
if ((l < ml) && (ml <= r)) {
return getOp().applyAsLong(v[id(l, ml)], fold(ml, r));
} else {
return getOp().applyAsLong(fold(l, mr), v[id(mr, r)]);
}
}
public long identity() {
return identity;
}
public long get(int i) {
return v[id(i, i + 1)];
}
public void dump() {
java.lang.System.out.println("セグメント木の各要素");
for (int w = 1; w <= n; w *= 2) {
for (int i = 0; i < w; ++i) {
java.lang.System.out.print((v[i + w] == identity() ? "e" : v[i + w]) + " ".repeat(n == w ? 1 : ((2 * n) / w) - 1));
}
java.lang.System.out.println();
}
java.lang.System.out.print("v=");
for (int i = 0; i < inputN; i++) {
long v = get(i);
java.lang.System.out.print((v == identity() ? "e" : v) + (i == (inputN - 1) ? "\n" : " "));
}
}
/**
*
* @return the op
*/
public java.util.function.LongBinaryOperator getOp() {
return op;
}
/**
*
* @param op
* the op to set
*/
public void setOp(java.util.function.LongBinaryOperator op) {
this.op = op;
}
}
// --- Original Code ---
// import java.io.IOException;
// import java.util.Arrays;
//
// import library.tools.FastScanner;
// import library.tools.MergeFiles;
// import library.tools.MyPrintWriter;
// import library.util.ArrayUtils;
// import library.util.segtree.MaxSeg;
// import library.util.segtree.SegTreeFactory;
//
// 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();
// }
//
// @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);
// // dp[i][j] = max(1 + dp[k][l] : k < i, P[k] < P[i], l < j, Q[l] < Q[j])
// // = max(1 + f[k][j] : k < i, P[k] < P[i])
// // f[i][j] = max(dp[i][l] : l < j, Q[l] < Q[j])
//
// long[][]dp=new long[N][N];
// MaxSeg[] fmax=new MaxSeg[N];
// MaxSeg[] gmax=new MaxSeg[N];
// for (int i = 0; i < N; i++) {
// fmax[i]=new MaxSeg(N);
// gmax[i]=new MaxSeg(N);
// }
//
// for (int i = 0; i < N; i++) {
// for (int j = 0; j < N; j++) {
// dp[i][j]=Math.max(dp[i][j], 1+Math.max(0, fmax[j].fold(0, P[i])));
// dp[i][j]=Math.max(dp[i][j], 1+Math.max(0, gmax[j].fold(P[i]+1, N)));
// }
// {
// //f[i][*]を更新
// var seg=SegTreeFactory.max(N);
// for (int j = 0; j < N; j++) {
// long fij=seg.fold(0, Q[j]);
// seg.set(Q[j], dp[i][j]);
// fmax[j].mul(P[i], fij);
// }
//
// }
// {
// //g[i][*]を更新
// var seg=SegTreeFactory.max(N);
// for (int j = 0; j < N; j++) {
// long gij=seg.fold(Q[j]+1, N);
// seg.set(Q[j], dp[i][j]);
// gmax[j].mul(P[i], gij);
// }
// }
// }
// pw.println(ArrayUtils.max(dp));
// }
//
// }
//
// void tr(Object... objects) {
// System.out.println(Arrays.deepToString(objects));
// }
//
// }
//
//
//
//
//