結果

問題 No.3017 交互浴
ユーザー tobisatistobisatis
提出日時 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);
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0