結果
| 問題 |
No.1095 Smallest Kadomatsu Subsequence
|
| コンテスト | |
| ユーザー |
 yk1095
|
| 提出日時 | 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 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 25 TLE * 5 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
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);
}
}
}