結果
問題 |
No.3164 [Chery 7th Tune B] La vie en rose
|
ユーザー |
|
提出日時 | 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/
ソースコード
#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; } }