結果
| 問題 |
No.1095 Smallest Kadomatsu Subsequence
|
| コンテスト | |
| ユーザー |
 bluemegane
|
| 提出日時 | 2020-06-27 17:28:10 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 8,836 bytes |
| コンパイル時間 | 1,107 ms |
| コンパイル使用メモリ | 109,312 KB |
| 実行使用メモリ | 54,112 KB |
| 最終ジャッジ日時 | 2024-07-05 18:00:41 |
| 合計ジャッジ時間 | 6,795 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | RE * 20 TLE * 1 -- * 9 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System.Collections.Generic;
using static System.Math;
using System;
public class SB_BinarySearchTree<T> where T : IComparable
{
public class Node
{
public T Value;
public Node LChild;
public Node RChild;
public int Count;
public Node(T v)
{
Value = v;
Count = 1;
}
}
static Random _rnd = new Random();
public static int Count(Node t)
{
return t == null ? 0 : t.Count;
}
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);
}
}
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 = 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 = Min(ret, idx);
t = t.LChild;
if (t == null) ret = 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);
}
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;
}
static void Enumerate(Node t, List<T> ret)
{
if (t == null) return;
Enumerate(t.LChild, ret);
ret.Add(t.Value);
Enumerate(t.RChild, ret);
}
}
public class Set<T> where T : IComparable
{
protected SB_BinarySearchTree<T>.Node _root;
public T this[int idx] { get { return 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));
}
}
public class MultiSet<T> : Set<T> where T : IComparable
{
public override void Insert(T v)
{
if (_root == null) _root = new SB_BinarySearchTree<T>.Node(v);
else _root = SB_BinarySearchTree<T>.Insert(_root, v);
}
}
public class Hello
{
static void Main()
{
var n = int.Parse(Console.ReadLine().Trim());
string[] line = Console.ReadLine().Trim().Split(' ');
var a = Array.ConvertAll(line, int.Parse);
var bL = new int[n];
var br = new int[n];
bL[0] = a[0];
br[n - 1] = a[n - 1];
for (int i = 1; i < n; i++)
{
if (a[i] < bL[i - 1]) bL[i] = a[i];
else bL[i] = bL[i - 1];
if (a[n - 1 - i] < br[n - i]) br[n - 1 - i] = a[n - 1 - i];
else br[n - 1 - i] = br[n - i];
}
var ans1 = getAns1(n, a, bL, br);
var ans2 = getAns2(n, a);
int ans;
if (ans1 == -1 && ans2 == -1) ans = -1;
else if (ans1 == -1) ans = ans2;
else if (ans2 == -1) ans = ans1;
else ans = Min(ans1, ans2);
Console.WriteLine(ans);
}
static int getAns2(int n, int[] a)
{
var ssL = new Set<int>();
var ssr = new Set<int>();
for (int i = 1; i < n; i++) ssr.Insert(a[i]);
var res = int.MaxValue;
for (int i = 1; i < n - 1; i++)
{
ssL.Insert(a[i - 1]);
ssr.Remove(a[i]);
var p = ssL.UpperBound(a[i]);
var p2 = ssr.UpperBound(a[i]);
if (p <= i - 1 && p2 <= n - 1 - i)
{
if (a[i] < ssL.ElementAt(p) && a[i] < ssr.ElementAt(p2))
{
res = Min(res, a[i] + ssL.ElementAt(p) + ssr.ElementAt(p2));
}
}
}
if (res == int.MaxValue) return -1;
else return res;
}
static int getAns1(int n, int[] a, int[] bL, int[] br)
{
var res = int.MaxValue;
for (int i = 1; i < n - 1; i++)
{
if (a[i] > bL[i - 1] && a[i] > br[i + 1])
{
var t = a[i] + bL[i - 1] + br[i + 1];
res = Min(res, t);
}
}
if (res == int.MaxValue) return -1;
else return res;
}
}