結果

問題 No.1095 Smallest Kadomatsu Subsequence
ユーザー yk1095yk1095
提出日時 2020-07-03 15:44:34
言語 C#(csc)
(csc 3.9.0)
結果
TLE  
実行時間 -
コード長 10,969 bytes
コンパイル時間 1,272 ms
コンパイル使用メモリ 117,552 KB
実行使用メモリ 63,040 KB
最終ジャッジ日時 2024-09-16 17:06:43
合計ジャッジ時間 6,859 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 32 ms
25,600 KB
testcase_01 AC 31 ms
19,712 KB
testcase_02 AC 31 ms
19,968 KB
testcase_03 AC 32 ms
19,968 KB
testcase_04 AC 32 ms
20,096 KB
testcase_05 AC 32 ms
20,096 KB
testcase_06 AC 32 ms
19,968 KB
testcase_07 AC 32 ms
20,096 KB
testcase_08 AC 32 ms
20,096 KB
testcase_09 AC 32 ms
20,224 KB
testcase_10 AC 31 ms
20,096 KB
testcase_11 AC 34 ms
19,968 KB
testcase_12 AC 32 ms
20,096 KB
testcase_13 AC 109 ms
26,112 KB
testcase_14 AC 112 ms
25,728 KB
testcase_15 AC 112 ms
25,984 KB
testcase_16 AC 111 ms
26,240 KB
testcase_17 AC 110 ms
25,856 KB
testcase_18 AC 110 ms
25,984 KB
testcase_19 AC 111 ms
25,984 KB
testcase_20 AC 110 ms
25,984 KB
testcase_21 AC 110 ms
26,112 KB
testcase_22 AC 113 ms
25,856 KB
testcase_23 TLE -
testcase_24 TLE -
testcase_25 TLE -
testcase_26 TLE -
testcase_27 TLE -
testcase_28 AC 856 ms
61,016 KB
testcase_29 AC 812 ms
58,680 KB
testcase_30 AC 1,538 ms
56,820 KB
testcase_31 AC 1,523 ms
54,668 KB
testcase_32 AC 1,599 ms
56,848 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

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);
        }
    }
}
0