結果

問題 No.3167 [Cherry 7th Tune C] Cut in Queue
ユーザー tobisatis
提出日時 2025-05-30 23:18:03
言語 C#
(.NET 8.0.404)
結果
WA  
実行時間 -
コード長 4,360 bytes
コンパイル時間 8,876 ms
コンパイル使用メモリ 171,376 KB
実行使用メモリ 287,252 KB
最終ジャッジ日時 2025-05-30 23:18:55
合計ジャッジ時間 46,282 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 4 WA * 39
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (106 ミリ秒)。
  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 az = n.Repeat(() => Int() - 1);
    var q = Int();
    var queries = new (int, int)[q];
    for (var i = 0; i < q; i++)
    {
        var kind = Int();
        var v = -1;
        if (kind != 2) v = Int() - 1;
        queries[i] = (kind, v);
    }

    var ll = new LinkedList<int>();
    var nodes = new LinkedListNode<int>[n + q];
    for (var i = 0; i < n + q; i++) nodes[i] = new(i);
    for (var i = 0; i < n; i++) ll.AddLast(nodes[az[i]]);
    {
        var b = n;
        for (var i = 0; i < q; i++)
        {
            var (t, v) = queries[i];
            if (t != 1) continue;
            if (v < 0) ll.AddLast(nodes[b]);
            else ll.AddBefore(nodes[v], nodes[b]);
            b++;
        }
    }
    var ft = new RangeAddPointGet<int>(n + q);
    var iz = new int[n + q];
    var la = new int[n + q];
    {
        var i = 0;
        var j = -1;
        foreach (var node in ll)
        {
            iz[node] = i;
            la[i] = node;
            if (node < n) j++;
            ft.Add(i, i + 1, j);
            i++;
        }
    }
    int At(int k)
    {
        var pass = n + q - 1;
        var fail = -1;
        while (pass - fail > 1)
        {
            var mid = (pass + fail) >> 1;
            if (ft.Get(mid) >= k) pass = mid;
            else fail = mid;
        }
        return pass;
    }
    var llj = At(n - 1);
    var ans = new List<int>();
    foreach (var (t, v) in queries)
    {
        if (t == 1)
        {
            if (v < 0)
            {
                ft.Add(++llj, n + q, 1);
            }
            else
            {
                var fti = iz[v];
                ft.Add(fti - 1, n + q, 1);
            }
        }
        if (t == 2)
        {
            var fti = At(0);
            ft.Add(fti, n + q, -1);
        }
        if (t == 3)
        {
            var fti = At(v);
            ans.Add(la[fti] + 1);
        }
    }
    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 FenwickTree<T> where T : INumber<T>
{
    readonly T[] _values;
    public FenwickTree(int length) { _values = new T[length + 2]; }
    public void Add(int i, T value)
    {
        var values = _values;
        while (i < values.Length)
        {
            values[i] += value;
            i += i & -i;
        }
    }
    public T Sum(int i)
    {
        var values = _values;
        var res = T.Zero;
        while (i > 0)
        {
            res += values[i];
            i -= i & -i;
        }
        return res;
    }
}

// [0..N)
class RangeAddPointGet<T> where T : INumber<T>
{
    public RangeAddPointGet(int length) { _data = new FenwickTree<T>(length); }
    public void Add(int l, int r, T value) // [l, r)
    {
        _data.Add(l + 1, value);
        _data.Add(r + 1, -value);
    }
    public T Get(int at) => _data.Sum(at + 1);
    readonly FenwickTree<T>_data;
}
0