結果
問題 | No.284 門松と魔法(2) |
ユーザー | 紙ぺーぱー |
提出日時 | 2015-09-15 02:11:49 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 919 ms / 5,000 ms |
コード長 | 7,724 bytes |
コンパイル時間 | 6,203 ms |
コンパイル使用メモリ | 109,884 KB |
実行使用メモリ | 53,908 KB |
最終ジャッジ日時 | 2023-09-26 12:01:31 |
合計ジャッジ時間 | 13,536 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 69 ms
21,804 KB |
testcase_01 | AC | 68 ms
21,752 KB |
testcase_02 | AC | 67 ms
19,816 KB |
testcase_03 | AC | 69 ms
23,644 KB |
testcase_04 | AC | 68 ms
21,668 KB |
testcase_05 | AC | 68 ms
21,784 KB |
testcase_06 | AC | 67 ms
21,772 KB |
testcase_07 | AC | 67 ms
21,684 KB |
testcase_08 | AC | 69 ms
23,740 KB |
testcase_09 | AC | 69 ms
23,700 KB |
testcase_10 | AC | 76 ms
19,788 KB |
testcase_11 | AC | 70 ms
21,848 KB |
testcase_12 | AC | 77 ms
22,020 KB |
testcase_13 | AC | 70 ms
21,788 KB |
testcase_14 | AC | 68 ms
19,616 KB |
testcase_15 | AC | 68 ms
23,724 KB |
testcase_16 | AC | 74 ms
19,872 KB |
testcase_17 | AC | 69 ms
21,788 KB |
testcase_18 | AC | 76 ms
24,004 KB |
testcase_19 | AC | 68 ms
21,596 KB |
testcase_20 | AC | 70 ms
21,700 KB |
testcase_21 | AC | 69 ms
21,740 KB |
testcase_22 | AC | 76 ms
21,840 KB |
testcase_23 | AC | 103 ms
24,404 KB |
testcase_24 | AC | 409 ms
29,860 KB |
testcase_25 | AC | 196 ms
23,840 KB |
testcase_26 | AC | 68 ms
21,784 KB |
testcase_27 | AC | 68 ms
23,780 KB |
testcase_28 | AC | 68 ms
23,712 KB |
testcase_29 | AC | 809 ms
37,156 KB |
testcase_30 | AC | 662 ms
33,948 KB |
testcase_31 | AC | 182 ms
26,508 KB |
testcase_32 | AC | 919 ms
53,512 KB |
testcase_33 | AC | 658 ms
43,360 KB |
testcase_34 | AC | 649 ms
53,908 KB |
testcase_35 | AC | 69 ms
23,704 KB |
testcase_36 | AC | 67 ms
21,712 KB |
testcase_37 | AC | 186 ms
26,356 KB |
testcase_38 | AC | 151 ms
25,848 KB |
testcase_39 | AC | 78 ms
21,876 KB |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System; using System.Linq; using System.Diagnostics; using System.Collections.Generic; using Debug = System.Diagnostics.Debug; using StringBuilder = System.Text.StringBuilder; using System.Numerics; namespace Program { public class Solver { /// <summary> /// O(NlogN) /// </summary> public void Solve() { //dp[prev,now]=lenをセグメント木でやる var n = int.Parse(Console.ReadLine()); var a = Console.ReadLine().Split().Select(int.Parse).ToArray(); var S = a.Distinct().ToList(); S.Add(-1); S.Add(int.MaxValue);//番兵 S.Sort(); for (int i = 0; i < n; i++) a[i] = S.BinarySearch(a[i]);//座圧 var sz = S.Count; var inc = new SegTree.SegmentTree(sz);//右端の2つの竹について単調増加な最長門松部分列 var dec = new SegTree.SegmentTree(sz);//右端の2つの竹について単調減少な最長門松部分列 inc.Update(sz - 1, 0, 0); dec.Update(0, 0, sz - 1); foreach (var i in a) { //下がる { var max = inc.Query(i + 1, sz, i);//prevがi以外であってnowがiより大きいもの var pos = max.J; var sec = Triplet.Max(inc.Query(i + 1, pos, i), inc.Query(pos + 1, sz, i));//pos以外から来て,prevがi以外であってnowがiより大きいもの dec.Update(i, max.I + 1, max.J);//dp[pos1,i]=dp[prev1,pos1]+1 dec.Update(i, sec.I + 1, sec.J);//dp[pos2,i]=dp[prev2,pos2]+1 } //上がる { var max = dec.Query(0, i, i);//prevがi以外であってnowがiより小さいもの var pos = max.J; var sec = Triplet.Max(dec.Query(0, pos, i), dec.Query(pos + 1, i, i));//pos以外から来て,prevがi以外であってnowがiより大きいもの inc.Update(i, max.I + 1, max.J);//dp[pos1,i]=dp[prev1,pos1]+1 inc.Update(i, sec.I + 1, sec.J);//dp[pos2,i]=dp[prev2,pos2]+1 } } var ans = Math.Max(inc.Query(0, sz, -1).I, dec.Query(0, sz, -1).I); if (ans < 3) ans = 0; Console.WriteLine(ans); } static T[] Enumerate<T>(int n, Func<int, T> f) { var a = new T[n]; for (int i = 0; i < n; ++i) a[i] = f(i); return a; } static public void Swap<T>(ref T a, ref T b) { var tmp = a; a = b; b = tmp; } } } #region main static class Ex { static public void Main() { var solver = new Program.Solver(); solver.Solve(); } } #endregion namespace SegTree { using K = Triplet<int, int, int>; #region SegTree [System.Diagnostics.DebuggerDisplay("Data={ToString()}")] public class SegmentTree { static public void Swap<T>(ref T a, ref T b) { var tmp = a; a = b; b = tmp; } readonly K min = new K(-1000000000, -1, -1); readonly Pair<K, K> MIN; int n; Pair<K, K>[] data;//length,now,prevのtripletのペア, public SegmentTree(int size) { MIN = new Pair<K, K>(min, min); n = 1; while (n < size) n <<= 1; data = new Pair<K, K>[n << 1]; for (int i = 0; i < n << 1; i++) data[i] = MIN; } /// <summary> /// 葉ノードについて,fromが一致しないようにlengthを最大化 /// </summary> void update(ref Pair<K, K> data, K t) { if (data.x.I < t.I) { if (data.x.K == t.K) data.x = t; else { data.y = data.x; data.x = t; } } else if (data.y.I < t.I) { if (data.x.K != t.K) data.y = t; } } /// <summary> /// k番目の葉ノードにfromからきたときに長さv /// </summary> public void Update(int k, int v, int from) { var t = new K(v, k, from); k += n; update(ref data[k], t); k >>= 1; while (k > 0) { update(ref data[k], t); k >>= 1; } } /// <summary> /// [a,b)のfromがnowでないようなlengthの最大値を求める. /// </summary> public K Query(int a, int b, int now) { return Query(a, b, now, 1, 0, n); } private K Query(int a, int b, int now, int k, int l, int r) { if (r <= a || b <= l) return min; if (a <= l && r <= b) { if (data[k].x.K != now) return data[k].x; else return data[k].y; } else { var vl = Query(a, b, now, k << 1, l, (l + r) >> 1); var vr = Query(a, b, now, (k << 1) + 1, (l + r) >> 1, r); return Triplet.Max(vl, vr); } } } #endregion } #region Triplet<ST,FT,TT> static public class Triplet { static public Triplet<FT, ST, TT> Create<FT, ST, TT>(FT f, ST s, TT t) where FT : IComparable<FT> where ST : IComparable<ST> where TT : IComparable<TT> { return new Triplet<FT, ST, TT>(f, s, t); } static public Triplet<FT, ST, TT> Min<FT, ST, TT>(Triplet<FT, ST, TT> p, Triplet<FT, ST, TT> q) where FT : IComparable<FT> where ST : IComparable<ST> where TT : IComparable<TT> { return (p.CompareTo(q) <= 0) ? p : q; } static public Triplet<FT, ST, TT> Max<FT, ST, TT>(Triplet<FT, ST, TT> p, Triplet<FT, ST, TT> q) where FT : IComparable<FT> where ST : IComparable<ST> where TT : IComparable<TT> { return (p.CompareTo(q) >= 0) ? p : q; } } public struct Triplet<FT, ST, TT> : IComparable<Triplet<FT, ST, TT>> where FT : IComparable<FT> where ST : IComparable<ST> where TT : IComparable<TT> { public FT I; public ST J; public TT K; public Triplet(FT i, ST j, TT k) : this() { I = i; J = j; K = k; } public int CompareTo(Triplet<FT, ST, TT> other) { var cmp = I.CompareTo(other.I); if (cmp != 0) return cmp; cmp = J.CompareTo(other.J); if (cmp != 0) return cmp; return K.CompareTo(other.K); } public override string ToString() { return string.Format("{0} {1} {2}", I, J, K); } } #endregion #region Compair static public class Pair { static public Pair<FT, ST> Create<FT, ST>(FT f, ST s) where FT : IComparable<FT> where ST : IComparable<ST> { return new Pair<FT, ST>(f, s); } static public Pair<FT, ST> Min<FT, ST>(Pair<FT, ST> p, Pair<FT, ST> q) where FT : IComparable<FT> where ST : IComparable<ST> { return (p.CompareTo(q) <= 0) ? p : q; } static public Pair<FT, ST> Max<FT, ST>(Pair<FT, ST> p, Pair<FT, ST> q) where FT : IComparable<FT> where ST : IComparable<ST> { return (p.CompareTo(q) >= 0) ? p : q; } } public struct Pair<FT, ST> : IComparable<Pair<FT, ST>> where FT : IComparable<FT> where ST : IComparable<ST> { public FT x; public ST y; public Pair(FT f, ST s) : this() { x = f; y = s; } public int CompareTo(Pair<FT, ST> other) { var cmp = x.CompareTo(other.x); return cmp != 0 ? cmp : y.CompareTo(other.y); } public override string ToString() { return string.Format("{0} {1}", x, y); } } #endregion