#505740 (C#(csc)) No.1095 Smallest Kadomatsu Subsequence

• 問題: No.1095 Smallest Kadomatsu Subsequence
• ユーザー: yk1095
• 提出日時: 2020-07-03 15:44:34
• 言語: C#(csc) (csc 3.9.0)
• 結果: TLE
• 実行時間: -
• コード長: 10,969 bytes
• コンパイル時間: 2,211 ms
• コンパイル使用メモリ: 64,388 KB
• 実行使用メモリ: 56,512 KB
• 最終ジャッジ日時: 2023-10-14 23:35:42
• 合計ジャッジ時間: 27,284 ms
• ジャッジサーバーID （参考情報）: judge15 / judge14

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	67 ms; 23,428 KB
testcase_01	AC	67 ms; 23,496 KB
testcase_02	AC	68 ms; 23,528 KB
testcase_03	AC	68 ms; 23,688 KB
testcase_04	AC	67 ms; 23,532 KB
testcase_05	AC	67 ms; 21,636 KB
testcase_06	AC	67 ms; 23,580 KB
testcase_07	AC	68 ms; 23,580 KB
testcase_08	AC	68 ms; 23,564 KB
testcase_09	AC	68 ms; 23,776 KB
testcase_10	AC	69 ms; 23,468 KB
testcase_11	AC	69 ms; 23,676 KB
testcase_12	AC	68 ms; 23,440 KB
testcase_13	AC	149 ms; 29,480 KB
testcase_14	AC	148 ms; 29,480 KB
testcase_15	AC	149 ms; 31,480 KB
testcase_16	AC	149 ms; 31,696 KB
testcase_17	AC	147 ms; 29,408 KB
testcase_18	AC	148 ms; 31,460 KB
testcase_19	AC	148 ms; 29,352 KB
testcase_20	AC	148 ms; 29,336 KB
testcase_21	AC	148 ms; 29,308 KB
testcase_22	AC	149 ms; 31,556 KB
testcase_23	TLE	-
testcase_24	TLE	-
testcase_25	TLE	-
testcase_26	TLE	-
testcase_27	TLE	-
testcase_28	AC	919 ms; 54,328 KB
testcase_29	AC	864 ms; 54,356 KB
testcase_30	AC	1,630 ms; 54,112 KB
testcase_31	AC	1,605 ms; 54,224 KB
testcase_32	AC	1,624 ms; 54,308 KB

ソースコード

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace AtCoder.A
{
    public class Program
    {
        public static void Main() { var r = GetResult(); Debug.WriteLine(r); Console.Write(r); }

        private static object GetResult()
        {
            var N = (int)ReadLong();
            var A = ReadLongs();

            var lowerMinLeftForAt = new long[N];
            lowerMinLeftForAt[0] = long.MaxValue;
            var upperMinLeftForAt = new long[N];
            var sortedFromLeft = new Set<long>();
            sortedFromLeft.Insert(A[0]);
            for (var i = 1; i < N; i++)
            {
                lowerMinLeftForAt[i] = Math.Min(lowerMinLeftForAt[i - 1], A[i - 1]);

                if (A[i] < sortedFromLeft.Max)
                {
                    var index = sortedFromLeft.LowerBound(A[i]);
                    upperMinLeftForAt[i] = sortedFromLeft[index];
                }
                else
                {
                    upperMinLeftForAt[i] = long.MaxValue;
                }
                // 次の判定用に追加
                sortedFromLeft.Insert(A[i]);
            }

            var lowerMinRightForAt = new long[N];
            lowerMinRightForAt[N - 1] = long.MaxValue;
            var upperMinRightForAt = new long[N];
            var sortedFromRight = new Set<long>();
            sortedFromRight.Insert(A[N - 1]);
            for (var i = N - 2; i >= 0; i--)
            {
                lowerMinRightForAt[i] = Math.Min(lowerMinRightForAt[i + 1], A[i + 1]);

                if (A[i] < sortedFromRight.Max)
                {
                    var index = sortedFromRight.LowerBound(A[i]);
                    upperMinRightForAt[i] = sortedFromRight[index];
                }
                else
                {
                    upperMinRightForAt[i] = long.MaxValue;
                }
                sortedFromRight.Insert(A[i]);
            }

            var min = long.MaxValue;
            for (var i = 1; i < N - 1; i++)
            {
                var b = A[i];

                if (lowerMinLeftForAt[i] != long.MaxValue && lowerMinRightForAt[i] != long.MaxValue
                    && b > lowerMinLeftForAt[i] && b > lowerMinRightForAt[i])
                {
                    min = Math.Min(min, lowerMinLeftForAt[i] + b + lowerMinRightForAt[i]);
                }
                if (upperMinLeftForAt[i] != long.MaxValue && upperMinRightForAt[i] != long.MaxValue
                    && b < upperMinLeftForAt[i] && b < upperMinRightForAt[i])
                {
                    min = Math.Min(min, upperMinLeftForAt[i] + b + upperMinRightForAt[i]);
                }
            }

            return min == long.MaxValue ? -1 : min;
        }

        #region Console

        public static string ReadText() { return Console.ReadLine(); }
        public static List<string> ReadTexts() { return Console.ReadLine().Split(' ').ToList(); }
        public static long ReadLong() { return long.Parse(Console.ReadLine()); }
        public static List<long> ReadLongs() { return Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToList(); }

        #endregion
    }
    /// <summary>
    /// C-like set
    /// </summary>
    public class Set<T> where T : IComparable
    {
        protected SB_BinarySearchTree<T>.Node _root;
        public T Max => this[Count() - 1];
        public T this[int idx] => ElementAt(idx);

        public int Count()
        {
            return SB_BinarySearchTree<T>.Count(_root);
        }

        public virtual void Insert(T v)
        {
            if (_root == null) _root = new SB_BinarySearchTree<T>.Node(v);
            else
            {
                if (SB_BinarySearchTree<T>.Find(_root, v) != null) return;
                _root = SB_BinarySearchTree<T>.Insert(_root, v);
            }
        }

        public void Clear()
        {
            _root = null;
        }

        public void Remove(T v)
        {
            _root = SB_BinarySearchTree<T>.Remove(_root, v);
        }

        public bool Contains(T v)
        {
            return SB_BinarySearchTree<T>.Contains(_root, v);
        }

        public T ElementAt(int k)
        {
            var node = SB_BinarySearchTree<T>.FindByIndex(_root, k);
            if (node == null) throw new IndexOutOfRangeException();
            return node.Value;
        }

        public int Count(T v)
        {
            return SB_BinarySearchTree<T>.UpperBound(_root, v) - SB_BinarySearchTree<T>.LowerBound(_root, v);
        }

        public int LowerBound(T v)
        {
            return SB_BinarySearchTree<T>.LowerBound(_root, v);
        }

        public int UpperBound(T v)
        {
            return SB_BinarySearchTree<T>.UpperBound(_root, v);
        }

        public Tuple<int, int> EqualRange(T v)
        {
            if (!Contains(v)) return new Tuple<int, int>(-1, -1);
            return new Tuple<int, int>(SB_BinarySearchTree<T>.LowerBound(_root, v), SB_BinarySearchTree<T>.UpperBound(_root, v) - 1);
        }

        public List<T> ToList()
        {
            return new List<T>(SB_BinarySearchTree<T>.Enumerate(_root));
        }
    }
    /// <summary>
    /// Self-Balancing Binary Search Tree
    /// (using Randamized BST)
    /// </summary>
    public class SB_BinarySearchTree<T> where T : IComparable
    {
        public class Node
        {
            public T Value;
            public Node LChild;
            public Node RChild;
            public int Count;     //size of the sub tree

            public Node(T v)
            {
                Value = v;
                Count = 1;
            }
        }

        private static readonly Random _rnd = new Random();

        public static int Count(Node t)
        {
            return t == null ? 0 : t.Count;
        }

        private static Node Update(Node t)
        {
            t.Count = Count(t.LChild) + Count(t.RChild) + 1;
            return t;
        }

        public static Node Merge(Node l, Node r)
        {
            if (l == null || r == null) return l == null ? r : l;

            if (Count(l) / (double)(Count(l) + Count(r)) > _rnd.NextDouble())
            {
                l.RChild = Merge(l.RChild, r);
                return Update(l);
            }
            else
            {
                r.LChild = Merge(l, r.LChild);
                return Update(r);
            }
        }

        /// <summary>
        /// split as [0, k), [k, n)
        /// </summary>
        public static Tuple<Node, Node> Split(Node t, int k)
        {
            if (t == null) return new Tuple<Node, Node>(null, null);
            if (k <= Count(t.LChild))
            {
                var s = Split(t.LChild, k);
                t.LChild = s.Item2;
                return new Tuple<Node, Node>(s.Item1, Update(t));
            }
            else
            {
                var s = Split(t.RChild, k - Count(t.LChild) - 1);
                t.RChild = s.Item1;
                return new Tuple<Node, Node>(Update(t), s.Item2);
            }
        }

        public static Node Remove(Node t, T v)
        {
            if (Find(t, v) == null) return t;
            return RemoveAt(t, LowerBound(t, v));
        }

        public static Node RemoveAt(Node t, int k)
        {
            var s = Split(t, k);
            var s2 = Split(s.Item2, 1);
            return Merge(s.Item1, s2.Item2);
        }

        public static bool Contains(Node t, T v)
        {
            return Find(t, v) != null;
        }

        public static Node Find(Node t, T v)
        {
            while (t != null)
            {
                var cmp = t.Value.CompareTo(v);
                if (cmp > 0) t = t.LChild;
                else if (cmp < 0) t = t.RChild;
                else break;
            }
            return t;
        }

        public static Node FindByIndex(Node t, int idx)
        {
            if (t == null) return null;

            var currentIdx = Count(t) - Count(t.RChild) - 1;
            while (t != null)
            {
                if (currentIdx == idx) return t;
                if (currentIdx > idx)
                {
                    t = t.LChild;
                    currentIdx -= (Count(t == null ? null : t.RChild) + 1);
                }
                else
                {
                    t = t.RChild;
                    currentIdx += (Count(t == null ? null : t.LChild) + 1);
                }
            }

            return null;
        }

        public static int UpperBound(Node t, T v)
        {
            var torg = t;
            if (t == null) return -1;

            var ret = int.MaxValue;
            var idx = Count(t) - Count(t.RChild) - 1;
            while (t != null)
            {
                var cmp = t.Value.CompareTo(v);

                if (cmp > 0)
                {
                    ret = Math.Min(ret, idx);
                    t = t.LChild;
                    idx -= (Count(t == null ? null : t.RChild) + 1);
                }
                else if (cmp <= 0)
                {
                    t = t.RChild;
                    idx += (Count(t == null ? null : t.LChild) + 1);
                }
            }
            return ret == int.MaxValue ? Count(torg) : ret;
        }

        public static int LowerBound(Node t, T v)
        {
            var torg = t;
            if (t == null) return -1;

            var idx = Count(t) - Count(t.RChild) - 1;
            var ret = int.MaxValue;
            while (t != null)
            {
                var cmp = t.Value.CompareTo(v);
                if (cmp >= 0)
                {
                    if (cmp == 0) ret = Math.Min(ret, idx);
                    t = t.LChild;
                    if (t == null) ret = Math.Min(ret, idx);
                    idx -= t == null ? 0 : (Count(t.RChild) + 1);
                }
                else if (cmp < 0)
                {
                    t = t.RChild;
                    idx += (Count(t == null ? null : t.LChild) + 1);
                    if (t == null) return idx;
                }
            }
            return ret == int.MaxValue ? Count(torg) : ret;
        }

        public static Node Insert(Node t, T v)
        {
            var ub = LowerBound(t, v);
            return InsertByIdx(t, ub, v);
        }

        private static Node InsertByIdx(Node t, int k, T v)
        {
            var s = Split(t, k);
            return Merge(Merge(s.Item1, new Node(v)), s.Item2);
        }

        public static IEnumerable<T> Enumerate(Node t)
        {
            var ret = new List<T>();
            Enumerate(t, ret);
            return ret;
        }

        private static void Enumerate(Node t, List<T> ret)
        {
            if (t == null) return;
            Enumerate(t.LChild, ret);
            ret.Add(t.Value);
            Enumerate(t.RChild, ret);
        }
    }
}