結果
問題 | No.284 門松と魔法(2) |
ユーザー |
|
提出日時 | 2017-08-18 13:45:07 |
言語 | D (dmd 2.109.1) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,283 bytes |
コンパイル時間 | 1,254 ms |
コンパイル使用メモリ | 129,580 KB |
実行使用メモリ | 12,848 KB |
最終ジャッジ日時 | 2024-06-12 21:36:09 |
合計ジャッジ時間 | 8,184 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 WA * 9 TLE * 1 -- * 10 |
ソースコード
import std.algorithm, std.conv, std.range, std.stdio, std.string;void main(){auto n = readln.chomp.to!size_t;auto a = new int[](n), rd = readln.chomp.splitter;foreach (i; 0..n) {a[i] = rd.front.to!int;rd.popFront();}compress(a);auto na = a.maxElement;auto st1 = SegmentTree!(Data[], [], merge)(na+1);auto st2 = SegmentTree!(Data[], [], merge)(na+1);foreach (ai; a) {auto m1 = st2[0..ai].filter!(d => d.prev != ai);auto m2 = st1[ai+1..$].filter!(d => d.prev != ai);auto d1 = m1.take(2).map!(d => Data(d.len+1, ai, d.curr)).array;st1[ai] = d1.empty ? [Data(1, ai, -1)] : d1;auto d2 = m2.take(2).map!(d => Data(d.len+1, ai, d.curr)).array;st2[ai] = d2.empty ? [Data(1, ai, -1)] : d2;}auto s1 = st1[0..$], r1 = s1.empty ? 0 : s1[0].len;auto s2 = st2[0..$], r2 = s2.empty ? 0 : s2[0].len;auto r = max(r1, r2);writeln(r <= 2 ? 0 : r);}auto compress(T)(ref T[] a){auto b = a.dup.sort().uniq, c = T(0);T[T] d;foreach (bi; b) d[bi] = c++;foreach (ref ai; a) ai = d[ai];}struct Data{int len;int curr;int prev;}auto merge(const Data[] a, const Data[] b){auto c = (a ~ b).dup.multiSort!("a.len > b.len", "a.prev > b.prev").uniq!"a.prev == b.prev";return c.take(3).array;}struct SegmentTree(T, T unit, alias pred = "a + b"){import core.bitop, std.functional;alias predFun = binaryFun!pred;const size_t n, an;T[] buf;this(size_t n){this.n = n;an = (1 << ((n - 1).bsr + 1));buf = new T[](an * 2);static if (T.init != unit) {buf[] = unit;}}this(T[] init){this(init.length);buf[an..an+n][] = init[];foreach_reverse (i; 1..an)buf[i] = predFun(buf[i*2], buf[i*2+1]);}void opIndexAssign(T val, size_t i){buf[i += an] = val;while (i /= 2)buf[i] = predFun(buf[i * 2], buf[i * 2 + 1]);}auto opSlice(size_t l, size_t r){l += an; r += an;T r1 = unit, r2 = unit;while (l != r) {if (l % 2) r1 = predFun(r1, buf[l++]);if (r % 2) r2 = predFun(buf[--r], r2);l /= 2; r /= 2;}return predFun(r1, r2);}pure size_t opDollar() const { return n; }pure auto opIndex(size_t i) const { return buf[i + an]; }}