結果

問題 No.3167 [Cherry 7th Tune C] Cut in Queue
ユーザー tobisatis
提出日時 2025-06-02 15:35:44
言語 C#
(.NET 8.0.404)
結果
AC  
実行時間 2,042 ms / 2,500 ms
コード長 7,962 bytes
コンパイル時間 8,179 ms
コンパイル使用メモリ 172,392 KB
実行使用メモリ 344,668 KB
最終ジャッジ日時 2025-06-02 15:36:42
合計ジャッジ時間 52,774 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 43
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (99 ミリ秒)。
  main -> /home/judge/data/code/bin/Release/net8.0/main.dll
  main -> /home/judge/data/code/bin/Release/net8.0/publish/

ソースコード

diff # 

#nullable enable

using System.Numerics;

void Run()
{
    var n = Int();
    var a = new FlexibleArray<int>(n.Repeat(Int));
    var ans = new List<int>();
    var l = n;
    var q = Int();
    for (var i = 0; i < q; i++)
    {
        var t = Int();
        if (t == 1)
        {
            var k = Int();
            if (k == 0) a.InsertAt(++l, a.Count);
            else
            {
                var j = a.FindIndex(k)!.Value;
                a.InsertAt(++l, j);
            }
        }
        else if (t == 2) a.DeleteAt(0);
        else
        {
            var k = Int() - 1;
            ans.Add(a.At(k));
        }
    }
    Out(ans);
}

#region
var _io_ = new AtCoderIO(){ Backend = new() };
Run();
_io_.Backend.Flush();

string String() => _io_.Next();
int Int() => int.Parse(String());
void Out(object? x, string? sep = null) => _io_.Out(x, sep);

class AtCoderIO
{
    public required StandardIOBackend Backend { get; init; }

    ReadOnlyMemory<string> _input = Array.Empty<string>();
    int _iter = 0;
    public string Next()
    {
        while (_iter >= _input.Length) (_input, _iter) = (Backend.ReadLine().Trim().Split(' '), 0);
        return _input.Span[_iter++];
    }

    public void Out(object? x, string? separator = null)
    {
        if (x == null) return;
        separator ??= Environment.NewLine;
        if (x is System.Collections.IEnumerable a and not string)
        {
            var objects = a.Cast<object>();
            if (separator == Environment.NewLine && !objects.Any()) return;
            x = string.Join(separator, objects);
        }
        Backend.WriteLine(x);
    }
}

class StandardIOBackend
{
    readonly StreamReader _sr = new(Console.OpenStandardInput());
    readonly StreamWriter _sw = new(Console.OpenStandardOutput()) { AutoFlush = false };
    public string ReadLine() => _sr.ReadLine()!;
    public void WriteLine(object? value) => _sw.WriteLine(value);
    public void Flush() => _sw.Flush();
}
#endregion

static class Extensions
{
    public static T[] Repeat<T>(this int time, Func<T> F) => Enumerable.Range(0, time).Select(_ => F()).ToArray();
}

class ScapegoatTree<T>
{
    protected class Node
    {
        public required T Data { get; set; }
        public Node? P { get; set; }
        public Node? L { get; set; }
        public Node? R { get; set; }
        public int Size { get; set; } = 1;

        public Node? this[bool i]
        {
            get => i ? R : L;
            set { if (i) R = value; else L = value; }
        }
    }

    protected readonly double _sizeFactor = 2.0 / 3;
    protected readonly double _heightFactor = -1.0 / Math.Log(2.0 / 3);
    protected Node? Root { get; set; }
    protected int _maxCount = 0;

    public T At(int index) => At(Root, index).Data;
    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? DeleteAtInternal(int index)
    {
        Node? deleted = null;
        var root = Root = DeleteAt(Root, null, ref deleted, index);
        if (root != null && Count < _sizeFactor * _maxCount)
        {
            Root = Rebuild(root, null);
            _maxCount = Count;
        }
        return deleted;
    }

    Node? DeleteAt(Node? node, Node? prev, ref Node? deleted, int index)
    {
        if (node == null) return null;
        var ls = Size(node.L);
        if (ls == index)
        {
            deleted = node;
            node = Merge(node.L, node.R, prev);
            if (node != null) Update(node);
            return node;
        }
        var right = index > ls;
        var li = right ? index - 1 - ls : index;
        node[right] = DeleteAt(node[right], node, ref deleted, li);
        Update(node);
        return node;
    }

    Node? Merge(Node? l, Node? r, Node? prev)
    {
        if (l == null)
        {
            if (r != null) r.P = prev;
            return r;
        }
        if (r == null)
        {
            l.P = prev;
            return l;
        }
        if (l.Size < r.Size)
        {
            r.L = Merge(l, r.L, r);
            r.P = prev;
            Update(r);
            return r;
        }
        else
        {
            l.R = Merge(l.R, r, l);
            l.P = prev;
            Update(l);
            return l;
        }
    }

    protected static Node Rebuild(Node node, Node? prev)
    {
        var len = node.Size;
        var nodes = new Node[len].AsSpan();
        var index = 0;
        Traverse(node, nodes, ref index);
        return Rebuild(nodes, 0, len, prev);
    }

    static void Traverse(Node? node, Span<Node> nodes, ref int i)
    {
        if (node == null) return;
        Traverse(node.L, nodes, ref i);
        nodes[i++] = node;
        Traverse(node.R, nodes, ref i);
    }
    
    protected static Node Rebuild(Span<Node> nodes, int l, int r, Node? prev)
    {
        var m = (l + r) >> 1;
        var res = nodes[m];
        res.P = prev;
        if (l < m) res.L = Rebuild(nodes, l, m, res);
        else res.L = null;
        if (m + 1 < r) res.R = Rebuild(nodes, m + 1, r, res);
        else res.R = null;
        Update(res);
        return res;
    }

    public int Count => Size(Root);

    protected static void Update(Node node) { node.Size = 1 + Size(node.L) + Size(node.R); }
    protected static int Size(Node? node) => node?.Size ?? 0;
}

class FlexibleArray<T> : ScapegoatTree<T> where T : notnull
{
    readonly Dictionary<T, HashSet<Node>> _reversed = new();

    public FlexibleArray(IReadOnlyList<T> values)
    {
        var span = values.Select(e => new Node(){ Data = e }).ToArray().AsSpan();
        for (var i = 0; i < span.Length; i++)
        {
            var node = span[i];
            if (_reversed.TryGetValue(node.Data, out var s)) s.Add(node);
            else _reversed[node.Data] = new(){ node };
        }
        Root = Rebuild(span, 0, span.Length, null);
    }

    public T this[int index]
    {
        get => At(Root, index).Data;
        set { InsertAt(value, index); }
    }

    public int? FindIndex(T value)
    {
        if (_reversed.TryGetValue(value, out var nodes) && nodes.Count > 0)
        {
            var node = nodes.First();
            var res = Size(node.L);
            while (true)
            {
                var p = node.P;
                if (p == null) break;
                if (p.R == node) res += Size(p.L) + 1;
                node = p;
            }
            return res;
        }
        return null;
    }

    public void InsertAt(T value, int index)
    {
        var balanced = true;
        var inserted = new Node(){ Data = value };
        Root = InsertAt(Root, null, inserted, 0, ref balanced, index);
        _maxCount = Math.Max(_maxCount, Size(Root));
        if (_reversed.TryGetValue(value, out var s)) s.Add(inserted);
        else _reversed[value] = new(){ inserted };
    }

    public void DeleteAt(int index)
    {
        var deleted = DeleteAtInternal(index);
        if (deleted != null && _reversed.TryGetValue(deleted.Data, out var s)) s.Remove(deleted);
    }

    Node InsertAt(Node? node, Node? prev, Node inserted, int depth, ref bool balanced, int index)
    {
        if (node == null)
        {
            inserted.P = prev;
            balanced = depth <= _heightFactor * Math.Log2(_maxCount + 2);
            return inserted;
        }
        var ls = Size(node.L);
        var right = index > ls;
        var li = right ? index - 1 - ls : index;
        node[right] = InsertAt(node[right], node, inserted, depth + 1, ref balanced, li);
        Update(node);
        if (balanced || Size(node[right]) <= _sizeFactor * node.Size) return node;
        balanced = true;
        return Rebuild(node, prev);
    }
}
0