結果
| 問題 |
No.2667 Constrained Permutation
|
| コンテスト | |
| ユーザー |
 tobisatis
|
| 提出日時 | 2024-03-08 22:38:12 |
| 言語 | C# (.NET 8.0.404) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 9,339 bytes |
| コンパイル時間 | 12,294 ms |
| コンパイル使用メモリ | 168,908 KB |
| 実行使用メモリ | 70,888 KB |
| 最終ジャッジ日時 | 2024-09-29 20:07:06 |
| 合計ジャッジ時間 | 15,626 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 1 WA * 12 TLE * 2 -- * 31 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (86 ms)。 MSBuild のバージョン 17.9.6+a4ecab324 (.NET) main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
namespace AtCoder;
#nullable enable
using System.Numerics;
static class Extensions
{
public static T[] Repeat<T>(this int time, Func<T> F) => Enumerable.Range(0, time).Select(_ => F()).ToArray();
}
abstract class SelfBalancingTreeBase<T>
{
protected class Node
{
public required T Data { get; set; }
public Node? L { get; set; }
public Node? R { get; set; }
public int Height { get; set; } = 1;
public int Size { get; set; } = 1;
public Node? this[bool right]
{
get => right ? R : L;
set { if (right) R = value; else L = value; }
}
}
protected static Node At(Node? node, int index)
{
while (node != null)
{
var ls = Size(node.L);
if (index == ls) return node;
var right = index > ls;
if (right) index -= ls + 1;
node = node[right];
}
throw new IndexOutOfRangeException();
}
protected Node? Root { get; set; }
protected static int Size(Node? node) => node?.Size ?? 0;
protected static int Height(Node? node) => node?.Height ?? 0;
protected static int HeightDiff(Node node) => Height(node.R) - Height(node.L);
protected static void Update(Node node)
{
node.Height = Math.Max(Height(node.L), Height(node.R)) + 1;
node.Size = Size(node.L) + Size(node.R) + 1;
}
protected static Node? DeleteMin(Node node, Node swap)
{
if (node.L == null) { swap.Data = node.Data; return node.R; }
node.L = DeleteMin(node.L, swap);
return Balance(node);
}
protected static Node Balance(Node node)
{
var diff = HeightDiff(node);
if (diff < -1 || 1 < diff)
{
var right = diff > 0;
var next = node[right]!;
if (HeightDiff(next) * diff < 0) node[right] = Rotate(next, right);
return Rotate(node, !right);
}
Update(node);
return node;
}
protected static Node Rotate(Node node, bool right)
{
var n0 = node[!right]!;
node[!right] = n0[right];
Update(node);
n0[right] = node;
Update(n0);
return n0;
}
public bool DeleteAt(int index) => Size(Root) != Size(Root = DeleteAt(Root, index));
static Node? DeleteAt(Node? node, int index)
{
if (node == null) return null;
var ls = Size(node.L);
if (index == ls)
{
if (node.R == null) return node.L;
node.R = DeleteMin(node.R, node);
}
else
{
var right = index > ls;
node[right] = DeleteAt(node[right], right ? index - 1 - ls : index);
}
return Balance(node);
}
protected IEnumerator<T> GetEnumerator()
{
var stack = new Stack<Node>();
var lastR = Root;
while (lastR != null || stack.Count > 0)
{
while (lastR != null)
{
stack.Push(lastR);
lastR = lastR.L;
}
var last = stack.Pop();
yield return last.Data;
lastR = last.R;
}
}
public int Count { get => Size(Root); }
}
abstract class SelfBalancingTree<TKey, TValue> : SelfBalancingTreeBase<KeyValuePair<TKey, TValue>> where TKey : IComparable<TKey>
{
public int MaxIndex(TKey key, bool include) => Bound(Root, key, true, include).Item1;
public int MinIndex(TKey key, bool include) => Bound(Root, key, false, include).Item1;
protected static (int, Node?) Bound(Node? node, TKey key, bool max, bool include)
{
var index = max ? -1 : 0;
Node? res = null;
while (node != null)
{
var comp = key.CompareTo(node.Data.Key);
var left = comp < 0 || comp == 0 && (max ^ include);
if (!left) index += Size(node.L) + 1;
if (max ^ left) res = node;
node = left ? node.L : node.R;
}
return (index, res);
}
public int CountKey(TKey key) => MaxIndex(key, true) - MaxIndex(key, false);
public ValueTuple<TKey>? MaxKey(TKey key, bool include) => ToOptionalKey(Bound(Root, key, true, include).Item2);
public ValueTuple<TKey>? MinKey(TKey key, bool include) => ToOptionalKey(Bound(Root, key, false, include).Item2);
static ValueTuple<TKey>? ToOptionalKey(Node? node) => node == null ? null : new(node.Data.Key);
protected static Node? Find(Node? node, TKey key)
{
var res = Bound(node, key, false, true).Item2;
return res != null && key.CompareTo(res.Data.Key) == 0 ? res : null;
}
protected static KeyValuePair<TKey, TValue> CreateData(TKey key, TValue value) => new(key, value);
protected void Insert(KeyValuePair<TKey, TValue> data) => Root = Insert(Root, data);
static Node Insert(Node? node, KeyValuePair<TKey, TValue> data)
{
if (node == null) return new Node{ Data = data };
var right = data.Key.CompareTo(node.Data.Key) >= 0;
node[right] = Insert(node[right], data);
return Balance(node);
}
public bool Delete(TKey key) => Size(Root) != Size(Root = Delete(Root, key));
static Node? Delete(Node? node, TKey key)
{
if (node == null) return null;
var comp = key.CompareTo(node.Data.Key);
if (comp == 0)
{
if (node.R == null) return node.L;
node.R = DeleteMin(node.R, node);
}
else
{
var right = comp > 0;
node[right] = Delete(node[right], key);
}
return Balance(node);
}
}
class OrderedMultiSet<T> : SelfBalancingTree<T, ValueTuple> where T : IComparable<T>
{
public bool Contains(T key) => Find(Root, key) != null;
public T At(int index) => At(Root, index).Data.Key;
public void Insert(T key) => Insert(CreateData(key, ValueTuple.Create()));
public new IEnumerator<T> GetEnumerator()
{
using var e = base.GetEnumerator();
while (e.MoveNext()) yield return e.Current.Key;
}
}
class AtCoder
{
object? Solve()
{
var n = Int();
var zz = n.Repeat(() => (Int(), Int()));
var pz = new int[n];
for (var i = 0; i < n; i++) pz[i] = i + 1;
bool F(int x)
{
var cz = new OrderedMultiSet<(int, int)>();
var evs = new List<(int, int, int)>();
for (var i = 0; i < n; i++)
{
var (l, r) = zz[i];
r -= x;
if (r < l) return false;
evs.Add((l, 3, r));
evs.Add((r, 30, l));
}
foreach (var t in pz) evs.Add((t, 10, 0));
evs.Sort();
foreach (var (t, kind, v) in evs)
{
if (kind == 3)
{
cz.Insert((t, v));
}
else if (kind == 30)
{
cz.Delete((v, t));
}
else
{
if (cz.Count == 0)
{
return false;
}
var (h, jdx) = cz.At(0);
if (h <= t)
{
cz.Delete((h, jdx));
continue;
}
return false;
}
}
return true;
}
int BinarySearch(int pass, int fail)
{
while (Math.Abs(pass - fail) > 1)
{
var middle = (pass + fail) >> 1;
if (F(middle)) pass = middle; else fail = middle;
}
return pass;
}
var rb = BinarySearch(-1, int.MaxValue / 2) + 1;
for (var i = 0; i < n; i++) pz[i] *= -1;
Array.Sort(pz);
for (var i = 0; i < n; i++)
{
var (l, r) = zz[i];
zz[i] = (-r, -l);
}
var lb = BinarySearch(-1, int.MaxValue / 2) + 1;
var ans = rb + lb;
return ans;
}
public static void Main() => new AtCoder().Run();
public void Run()
{
var res = Solve();
if (res != null)
{
if (res is bool yes) res = yes ? "Yes" : "No";
sw.WriteLine(res);
}
sw.Flush();
}
string[] input = Array.Empty<string>();
int iter = 0;
readonly StreamWriter sw = new(Console.OpenStandardOutput()) { AutoFlush = false };
#pragma warning disable IDE0051
string String()
{
while (iter >= input.Length) (input, iter) = (Console.ReadLine()!.Split(' '), 0);
return input[iter++];
}
T Input<T>() where T : IParsable<T> => T.Parse(String(), null);
int Int() => Input<int>();
void Out(object? x, string? separator = null)
{
separator ??= Environment.NewLine;
if (x is System.Collections.IEnumerable obj and not string)
{
var firstLine = true;
foreach (var item in obj)
{
if (!firstLine) sw.Write(separator);
firstLine = false;
sw.Write(item);
}
}
else sw.Write(x);
sw.WriteLine();
}
#pragma warning restore IDE0051
}