結果

問題 No.284 門松と魔法(2)
ユーザー 👑 hos.lyrichos.lyric
提出日時 2020-03-27 13:16:55
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 675 ms / 5,000 ms
コード長 5,165 bytes
コンパイル時間 1,915 ms
コンパイル使用メモリ 164,128 KB
実行使用メモリ 122,100 KB
最終ジャッジ日時 2024-06-22 05:49:50
合計ジャッジ時間 5,739 ms
ジャッジサーバーID
(参考情報)
judge3 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import std.conv, std.functional, std.range, std.stdio, std.string;
import std.algorithm, std.array, std.bigint, std.bitmanip, std.complex, std.container, std.math, std.mathspecial, std.numeric, std.regex, std
    .typecons;
import core.bitop;
class EOFException : Throwable { this() { super("EOF"); } }
string[] tokens;
string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens
    .popFront; return token; }
int readInt() { return readToken.to!int; }
long readLong() { return readToken.to!long; }
real readReal() { return readToken.to!real; }
bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } }
bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } }
int binarySearch(alias pred, T)(in T[] as) { int lo = -1, hi = cast(int)(as.length); for (; lo + 1 < hi; ) { const mid = (lo + hi) >> 1;
    (unaryFun!pred(as[mid]) ? hi : lo) = mid; } return hi; }
int lowerBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a >= val)); }
int upperBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a > val)); }
class Info {
int[2] val, bef, pos;
this() {
val[] = 0;
bef[] = -1;
pos[] = -1;
}
override string toString() const {
return format("(%s,%s,%s; %s,%s,%s)", val[0], bef[0], pos[0], val[1], bef[1], pos[1]);
}
}
Info mul(const(Info) p, const(Info) q) {
Info ret = new Info();
int s = 0, t = 0;
if (p.val[s] > q.val[t]) {
ret.val[0] = p.val[s];
ret.bef[0] = p.bef[s];
ret.pos[0] = p.pos[s];
++s;
} else {
ret.val[0] = q.val[t];
ret.bef[0] = q.bef[t];
ret.pos[0] = q.pos[t];
++t;
}
for (; s < 2 || t < 2; ) {
if (s < 2 && (t == 2 || p.val[s] > q.val[t])) {
if (ret.bef[0] != p.bef[s]) {
ret.val[1] = p.val[s];
ret.bef[1] = p.bef[s];
ret.pos[1] = p.pos[s];
break;
}
++s;
} else {
if (ret.bef[0] != q.bef[t]) {
ret.val[1] = q.val[t];
ret.bef[1] = q.bef[t];
ret.pos[1] = q.pos[t];
break;
}
++t;
}
}
return ret;
}
int segN;
void update(Info[] seg, int a, Info val) {
a += segN;
seg[a] = mul(seg[a], val);
for (; a >>= 1; ) {
seg[a] = mul(seg[a << 1], seg[a << 1 | 1]);
}
}
alias Result = Tuple!(int, "val", int, "pos");
Result rangeMax(Info[] seg, int a, int b, int key) {
Result ret = Result(0, -1);
void check(int c) {
const s = (seg[c].bef[0] != key) ? 0 : 1;
chmax(ret, Result(seg[c].val[s], seg[c].pos[s]));
}
for (a += segN, b += segN; a < b; a >>= 1, b >>= 1) {
if (a & 1) check(a++);
if (b & 1) check(--b);
}
return ret;
}
void main() {
try {
for (; ; ) {
const N = readInt();
auto A = new int[N];
foreach (i; 0 .. N) {
A[i] = readInt();
}
debug {
auto brt = new int[][](N, N);
foreach (i; 0 .. N) {
foreach (j; 0 .. i) {
if (A[j] != A[i]) {
chmax(brt[i][j], 2);
}
foreach (k; 0 .. j) {
if (((A[k] < A[j] && A[j] > A[i]) || (A[k] > A[j] && A[j] < A[i])) && A[k] != A[i]) {
chmax(brt[i][j], brt[j][k] + 1);
}
}
}
}
writeln("brt = ");
foreach (i; 0 .. N) {
writeln(i, ": ", brt[i]);
}
int mx;
foreach (i; 0 .. N) foreach (j; 0 .. i) {
chmax(mx, brt[i][j]);
}
writeln("brute: ", (mx < 3) ? 0 : mx);
}
auto as = A.dup.sort.uniq.array;
const asLen = cast(int)(as.length);
for (segN = 1; segN < asLen; segN <<= 1) {}
auto segU = new Info[segN << 1];
auto segD = new Info[segN << 1];
segU[] = new Info();
segD[] = new Info();
int ans;
foreach (i; 0 .. N) {
const pos = as.lowerBound(A[i]);
Info dpU = new Info();
const resD0 = segD.rangeMax(0, pos, pos);
dpU.val[0] = resD0.val + 1;
dpU.bef[0] = resD0.pos;
dpU.pos[0] = pos;
if (resD0.pos != -1) {
const resD1 = max(segD.rangeMax(0, resD0.pos, pos), segD.rangeMax(resD0.pos + 1, pos, pos));
dpU.val[1] = resD1.val + 1;
dpU.bef[1] = resD1.pos;
dpU.pos[1] = pos;
}
Info dpD = new Info();
const resU0 = segU.rangeMax(pos + 1, asLen, pos);
dpD.val[0] = resU0.val + 1;
dpD.bef[0] = resU0.pos;
dpD.pos[0] = pos;
if (resU0.pos != -1) {
const resU1 = max(segU.rangeMax(pos + 1, resU0.pos, pos), segU.rangeMax(resU0.pos + 1, asLen, pos));
dpD.val[1] = resU1.val + 1;
dpD.bef[1] = resU1.pos;
dpD.pos[1] = pos;
}
segU.update(pos, dpU);
segD.update(pos, dpD);
chmax(ans, dpU.val[0]);
chmax(ans, dpD.val[0]);
debug {
writeln(i, ": ", pos, " ", dpU, " ", dpD);
// writeln("segU = ", segU);
// writeln("segD = ", segD);
}
}
writeln((ans < 3) ? 0 : ans);
}
} catch (EOFException e) {
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0