結果
問題 | No.284 門松と魔法(2) |
ユーザー |
👑 |
提出日時 | 2020-03-27 13:09:41 |
言語 | D (dmd 2.109.1) |
結果 |
WA
|
実行時間 | - |
コード長 | 5,163 bytes |
コンパイル時間 | 1,985 ms |
コンパイル使用メモリ | 169,964 KB |
実行使用メモリ | 196,580 KB |
最終ジャッジ日時 | 2024-06-22 05:48:50 |
合計ジャッジ時間 | 8,955 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | WA * 23 TLE * 1 -- * 16 |
ソースコード
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(brt[i]);}int mx;foreach (i; 0 .. N) foreach (j; 0 .. i) {chmax(mx, brt[i][j]);}writeln((mx < 3) ? 0 : mx);continue;// }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 = min(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 = min(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) {}}