結果

問題 No.3017 交互浴
ユーザー tobisatis
提出日時 2025-01-25 14:36:50
言語 C#
(.NET 8.0.404)
結果
AC  
実行時間 1,698 ms / 2,000 ms
コード長 7,236 bytes
コンパイル時間 9,061 ms
コンパイル使用メモリ 174,884 KB
実行使用メモリ 259,652 KB
最終ジャッジ日時 2025-01-25 23:25:37
合計ジャッジ時間 89,419 ms
ジャッジサーバーID
（参考情報） 		judge7 / judge11
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 55
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (113 ミリ秒)。
  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;

object? Solve()
{
    var n = Int();
    var hz = n.Repeat(Int);

    var (vto, ov) = hz.Compress();
    var c = vto.Count;
    var op = new Op();
    var init = new (int, int, int)[c];
    {
        var l = 0;
        for (var i = 0; i < c; i++)
        {
            var v = ov[i];
            init[i] = (v - l, -1, 0);
            l = v;
        }
    }
    var lst = new LazySegmentTree<(int, int, int), int, Op>(init, op);
    var ans = new int[n];
    for (var i = 0; i < n; i++)
    {
        var h = hz[i];
        var j = vto[h];
        var color = i % 2 == 0 ? 1 : 0;
        lst.Apply(0, j + 1, color);
        ans[i] = lst.Product(0, c).Item3;
    }
    Out(ans);
    return null;
}

#region
AtCoderIO _io_;
var _backend_ = new StandardIOBackend();
_io_ = new(){ Backend = _backend_ };
Out(Solve());
_backend_.Flush();

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

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

    Memory<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)
    {
        if (x == null) return;
        if (x is System.Collections.IEnumerable a and not string)
        {
            var objects = a.Cast<object>();
            if (!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 (Dictionary<T, int> valueToOrder, List<T> orderedValues) Compress<T>(this IEnumerable<T> values) where T : IComparable<T>
    {
        var ordered = values.Distinct().OrderBy(self => self);
        return (ordered.Select((item, i) => (item, i)).ToDictionary(pair => pair.item, pair => pair.i), ordered.ToList());
    }

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

interface ISegmentTreeOperator<TMonoid>
{
    TMonoid IdentityElement { get; }
    TMonoid Operation(TMonoid x, TMonoid y);
}
partial class SegmentTree<TMonoid, TOperator> where TOperator : struct, ISegmentTreeOperator<TMonoid>
{
    public int BaseSize { get; init; }
    protected int Height { get; init; }
    protected TOperator Op { get; init; }
    protected TMonoid[] Values { get; init; }

    public SegmentTree(TMonoid[] initial, TOperator op = default)
    {
        Op = op;
        (BaseSize, Height) = (1, 0);
        while (BaseSize < initial.Length) (BaseSize, Height) = (BaseSize << 1, Height + 1);
        var size = BaseSize << 1;
        Values = new TMonoid[size];
        var values = Values.AsSpan();
        for (var i = 0; i < size; i++) values[i] = op.IdentityElement;
        for (var i = 0; i < initial.Length; i++) values[i + BaseSize] = initial[i];
        for (var i = BaseSize - 1; i > 0; i--) Update(values, i);
    }

    public TMonoid Product(int l, int r)
    {
        (l, r) = (l + BaseSize, r + BaseSize);
        var (resL, resR) = (Op.IdentityElement, Op.IdentityElement);
        var values = Values.AsSpan();
        while (l < r)
        {
            if ((l & 1) == 1) resL = Op.Operation(resL, values[l++]);
            if ((r & 1) == 1) resR = Op.Operation(values[--r], resR);
            (l, r) = (l >> 1, r >> 1);
        }
        return Op.Operation(resL, resR);
    }

    public void Set(int index, TMonoid value)
    {
        var j = index + BaseSize;
        var values = Values.AsSpan();
        values[j] = value;
        for (var i = 1; i <= Height; i++) Update(values, j >> i);
    }

    protected void Update(Span<TMonoid> values, int k) { values[k] = Op.Operation(values[k << 1], values[(k << 1) + 1]); }
}

interface ILazySegmentTreeOperator<TMonoid, TFunction> : ISegmentTreeOperator<TMonoid>
{
    TFunction IdentityFunction { get; }
    TMonoid Mapping(TFunction f, TMonoid x);
    TFunction Composition(TFunction f, TFunction g);
}
class LazySegmentTree<TMonoid, TFunction, TOperator> : SegmentTree<TMonoid, TOperator> where TOperator : struct, ILazySegmentTreeOperator<TMonoid, TFunction>
{
    TFunction[] Lazy { get; init; }

    public LazySegmentTree(TMonoid[] initial, TOperator op = default) : base(initial, op)
    {
        var size = BaseSize << 1;
        Lazy = new TFunction[size];
        for (var i = 0; i < size; i++) Lazy[i] = op.IdentityFunction;
    }

    public new TMonoid Product(int l, int r)
    {
        if (l == r) return Op.IdentityElement;
        Ascend(l, r);
        return base.Product(l, r);
    }

    public new void Set(int index, TMonoid value)
    {
        var j = index + BaseSize;
        for (var i = Height; i >= 1; i--) Propagate(j >> i);
        var values = Values.AsSpan();
        values[j] = value;
        for (var i = 1; i <= Height; i++) Update(values, j >> i);
    }

    public void Apply(int l, int r, TFunction f)
    {
        if (l == r) return;
        Ascend(l, r);
        (l, r) = (l + BaseSize, r + BaseSize);
        var (l2, r2) = (l, r);
        while (l2 < r2)
        {
            if ((l2 & 1) == 1) Apply(l2++, f);
            if ((r2 & 1) == 1) Apply(--r2, f);
            (l2, r2) = (l2 >> 1, r2 >> 1);
        }
        var values = Values.AsSpan();
        for (int i = 1; i <= Height; i++)
        {
            if (((l >> i) << i) != l) Update(values, l >> i);
            if (((r >> i) << i) != r) Update(values, (r - 1) >> i);
        }
    }

    void Ascend(int l, int r)
    {
        (l, r) = (l + BaseSize, r + BaseSize);
        for (int i = Height; i >= 1; i--)
        {
            if (((l >> i) << i) != l) Propagate(l >> i);
            if (((r >> i) << i) != r) Propagate((r - 1) >> i);
        }
    }
    void Propagate(int k)
    {
        Apply(k << 1, Lazy[k]);
        Apply((k << 1) + 1, Lazy[k]);
        Lazy[k] = Op.IdentityFunction;
    }
    void Apply(int k, TFunction f)
    {
        Values[k] = Op.Mapping(f, Values[k]);
        if (k < BaseSize) Lazy[k] = Op.Composition(Lazy[k], f);
    }
}

readonly struct Op : ILazySegmentTreeOperator<(int, int, int), int>
{
    public int IdentityFunction => -1;
    public (int, int, int) IdentityElement => (0, -1, 0);
    public int Composition(int f, int g) => g < 0 ? f : g;
    public (int, int, int) Mapping(int f, (int, int, int) x)
    {
        if (f < 0) return x;
        var (xc, _, _) = x;
        return (xc, f, f == 0 ? 0 : xc);
    }
    public (int, int, int) Operation((int, int, int) x, (int, int, int) y)
    {
        var (xc, xs, xv) = x;
        var (yc, ys, yv) = y;
        var ns = -1;
        if (xs == ys) ns = xs;
        return (xc + yc, ns, xv + yv);
    }
}
0