結果
問題 | No.3017 交互浴 |
ユーザー |
|
提出日時 | 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/
ソースコード
#nullable enableusing 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;}#regionAtCoderIO _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();}#endregionstatic 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);}}