結果

問題 No.3164 [Chery 7th Tune B] La vie en rose
コンテスト
ユーザー tobisatis
提出日時 2025-05-30 21:47:56
言語 C#
(.NET 8.0.404)
結果
AC  
実行時間 440 ms / 2,000 ms
コード長 4,928 bytes
コンパイル時間 10,391 ms
コンパイル使用メモリ 171,608 KB
実行使用メモリ 190,588 KB
最終ジャッジ日時 2025-05-30 21:48:24
合計ジャッジ時間 24,318 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 34
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (104 ミリ秒)。
  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);
    var q = Int();
    var queries = q.Repeat(() => (Int() - 1, Int()));

    var sz = new long[n + 1];
    for (var i = 0; i < n; i++) sz[i + 1] = sz[i] + az[i];
    var t = new WordSizeTree((uint)n + 2);
    t.Insert(0);
    t.Insert((uint)n + 1);
    for (var i = 0; i < n; i++) if (az[i] == 0) t.Insert((uint)i + 1);
    var ans = new long[q];
    for (var i = 0; i < q; i++)
    {
        var (x, b) = queries[i];
        var z = az[x] == 0;
        if (z) t.Delete((uint)x + 1);
        var l = t.Prev((uint)x + 1);
        var r = t.Next((uint)x + 1);
        ans[i] += b - az[x];
        if (r != null) ans[i] += sz[r.Value - 1];
        if (l != null) ans[i] -= sz[l.Value];
        if (z) t.Insert((uint)x + 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().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 WordSizeTree
{
    readonly ulong[][] _data;

    public WordSizeTree(uint size)
    {
        if (size == 0 || size > (1U << 30)) throw new ArgumentOutOfRangeException(nameof(size));
        var d = 0;
        size--;
        while (size > 0) (d, size) = (d + 1, size >> 6);
        _data = new ulong[d][];
        for (var i = 0; i < d; i++) _data[^(i + 1)] = new ulong[1 << (i * 6)];
    }

    public int Count { get; private set; } = 0;

    public void Insert(uint value)
    {
        if (Contains(value)) return;
        Count++;
        for (var i = 0; i < _data.Length; i++)
        {
            var (p, q) = (value >> 6, value & 63);
            _data[i][p] |= 1UL << (int)q;
            value = p;
        }
    }

    public void Delete(uint value)
    {
        if (!Contains(value)) return;
        Count--;
        for (var i = 0; i < _data.Length; i++)
        {
            var (p, q) = (value >> 6, value & 63);
            var b = 1UL << (int)q;
            _data[i][p] &= ~b;
            if (_data[i][p] > 0) break;
            value = p;
        }
    }

    public bool Contains(uint value)
    {
        var (p, q) = (value >> 6, value & 63);
        return ((_data[0][p] >> (int)q) & 1) > 0;
    }

    public uint? Next(uint value)
    {
        for (var i = 0; i < _data.Length; i++)
        {
            var (p, q) = (value >> 6, value & 63);
            if (p >= _data[i].Length) break;
            var k = _data[i][p] >> (int)q;
            if (k > 0)
            {
                value += (uint)System.Numerics.BitOperations.TrailingZeroCount(k);
                while (i > 0)
                {
                    k = _data[--i][value];
                    value <<= 6;
                    value += (uint)System.Numerics.BitOperations.TrailingZeroCount(k);
                }
                return value;
            }
            value = p + 1;
        }
        return null;
    }

    public uint? Prev(uint value)
    {
        for (var i = 0; i < _data.Length; i++)
        {
            var (p, q) = (value >> 6, value & 63);
            var k = _data[i][p] << (int)(63 - q);
            if (k > 0)
            {
                value -= (uint)System.Numerics.BitOperations.LeadingZeroCount(k);
                while (i > 0)
                {
                    k = _data[--i][value];
                    value <<= 6;
                    value += 63U - (uint)System.Numerics.BitOperations.LeadingZeroCount(k);
                }
                return value;
            }
            if (p == 0) break;
            value = p - 1;
        }
        return null;
    }
}
0