結果
問題 | No.3017 交互浴 |
ユーザー |
![]() |
提出日時 | 2025-01-25 13:12:09 |
言語 | C# (.NET 8.0.404) |
結果 |
AC
|
実行時間 | 1,777 ms / 2,000 ms |
コード長 | 23,288 bytes |
コンパイル時間 | 15,124 ms |
コンパイル使用メモリ | 170,624 KB |
実行使用メモリ | 213,044 KB |
最終ジャッジ日時 | 2025-01-25 22:38:59 |
合計ジャッジ時間 | 85,900 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 55 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (86 ミリ秒)。 main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
using System; using System.Collections.Generic; using System.IO; using System.Linq; using static System.Math; using System.Text; using System.Threading; using System.Globalization; using System.Runtime.CompilerServices; using System.Runtime.InteropServices; using Library; namespace Program { public static class ProblemE { static bool SAIKI = false; static public int numberOfRandomCases = 0; static public void MakeTestCase(List<string> _input, List<string> _output, ref Func<string[], bool> _outputChecker) { } static public void Solve() { var N = NN; var HList = NNList(N); var seg = new LIB_DynamicLazySegTree<long, long>(0, -1, (x, y) => x + y, (x, y, l, r) => y * (r - l), (x, y) => y); var ki = true; foreach (var item in HList) { if (ki) seg.Update(0, item, 1); else seg.Update(0, item, 0); Console.WriteLine(seg.Query(0, 10000000001)); ki = !ki; } } class Printer : StreamWriter { public override IFormatProvider FormatProvider { get { return CultureInfo.InvariantCulture; } } public Printer(Stream stream) : base(stream, new UTF8Encoding(false, true)) { base.AutoFlush = false; } public Printer(Stream stream, Encoding encoding) : base(stream, encoding) { base.AutoFlush = false; } } static LIB_FastIO fastio = new LIB_FastIODebug(); static string[] args; static public void Main(string[] args_t) { args = args_t; if (args_t.Length == 0) { fastio = new LIB_FastIO(); Console.SetOut(new Printer(Console.OpenStandardOutput())); } if (SAIKI) { var t = new Thread(Solve, 134217728); t.Start(); t.Join(); } else Solve(); Console.Out.Flush(); } static long NN => fastio.Long(); static double ND => fastio.Double(); static string NS => fastio.Scan(); static long[] NNList(long N) => Repeat(0, N).Select(_ => NN).ToArray(); static double[] NDList(long N) => Repeat(0, N).Select(_ => ND).ToArray(); static string[] NSList(long N) => Repeat(0, N).Select(_ => NS).ToArray(); static long Count<T>(this IEnumerable<T> x, Func<T, bool> pred) => Enumerable.Count(x, pred); static IEnumerable<T> Repeat<T>(T v, long n) => Enumerable.Repeat<T>(v, (int)n); static IEnumerable<int> Range(long s, long c) => Enumerable.Range((int)s, (int)c); static IOrderedEnumerable<T> OrderByRand<T>(this IEnumerable<T> x) => Enumerable.OrderBy(x, _ => xorshift); static IOrderedEnumerable<T> OrderBy<T>(this IEnumerable<T> x) => Enumerable.OrderBy(x.OrderByRand(), e => e); static IOrderedEnumerable<T1> OrderBy<T1, T2>(this IEnumerable<T1> x, Func<T1, T2> selector) => Enumerable.OrderBy(x.OrderByRand(), selector); static IOrderedEnumerable<T> OrderByDescending<T>(this IEnumerable<T> x) => Enumerable.OrderByDescending(x.OrderByRand(), e => e); static IOrderedEnumerable<T1> OrderByDescending<T1, T2>(this IEnumerable<T1> x, Func<T1, T2> selector) => Enumerable.OrderByDescending(x.OrderByRand(), selector); static IOrderedEnumerable<string> OrderBy(this IEnumerable<string> x) => x.OrderByRand().OrderBy(e => e, StringComparer.OrdinalIgnoreCase); static IOrderedEnumerable<T> OrderBy<T>(this IEnumerable<T> x, Func<T, string> selector) => x.OrderByRand().OrderBy(selector, StringComparer.OrdinalIgnoreCase); static IOrderedEnumerable<string> OrderByDescending(this IEnumerable<string> x) => x.OrderByRand().OrderByDescending(e => e, StringComparer.OrdinalIgnoreCase); static IOrderedEnumerable<T> OrderByDescending<T>(this IEnumerable<T> x, Func<T, string> selector) => x.OrderByRand().OrderByDescending(selector, StringComparer.OrdinalIgnoreCase); static string Join<T>(this IEnumerable<T> x, string separator = "") => string.Join(separator, x); static uint xorshift { get { _xsi.MoveNext(); return _xsi.Current; } } static IEnumerator<uint> _xsi = _xsc(); static IEnumerator<uint> _xsc() { uint x = 123456789, y = 362436069, z = 521288629, w = (uint)(DateTime.Now.Ticks & 0xffffffff); while (true) { var t = x ^ (x << 11); x = y; y = z; z = w; w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); yield return w; } } static bool Chmax<T>(this ref T lhs, T rhs) where T : struct, IComparable<T> { if (lhs.CompareTo(rhs) < 0) { lhs = rhs; return true; } return false; } static bool Chmin<T>(this ref T lhs, T rhs) where T : struct, IComparable<T> { if (lhs.CompareTo(rhs) > 0) { lhs = rhs; return true; } return false; } static void Fill<T>(this T[] array, T value) => array.AsSpan().Fill(value); static void Fill<T>(this T[,] array, T value) => MemoryMarshal.CreateSpan(ref array[0, 0], array.Length).Fill(value); static void Fill<T>(this T[,,] array, T value) => MemoryMarshal.CreateSpan(ref array[0, 0, 0], array.Length).Fill(value); static void Fill<T>(this T[,,,] array, T value) => MemoryMarshal.CreateSpan(ref array[0, 0, 0, 0], array.Length).Fill(value); } } namespace Library { class LIB_DynamicLazySegTree<T, E> where E : IEquatable<E> { class Node { public Node left; public Node right; public E val; public T dat; public E lazy; public long nodeL; public long subtreeL; public long nodeR; public long subtreeR; public bool isBlack; public bool needRecalc; } Func<T, T, T> f; Func<T, E, long, long, T> g; Func<E, E, E> h; T ti; E ei; Node root; bool isNeedFix; Node lmax; Node[] pool; int poolLength; public long MaxKey { [MethodImpl(MethodImplOptions.AggressiveInlining)] get; [MethodImpl(MethodImplOptions.AggressiveInlining)] private set; } public long MinKey { [MethodImpl(MethodImplOptions.AggressiveInlining)] get; [MethodImpl(MethodImplOptions.AggressiveInlining)] private set; } public LIB_DynamicLazySegTree(T ti, E ei, Func<T, T, T> f, Func<T, E, long, long, T> g, Func<E, E, E> h) { MinKey = long.MaxValue; MaxKey = long.MinValue; this.ti = ti; this.ei = ei; this.f = f; this.g = g; this.h = h; pool = new Node[32]; } [MethodImpl(MethodImplOptions.AggressiveInlining)] bool IsRed(Node n) => n != null && !n.isBlack; [MethodImpl(MethodImplOptions.AggressiveInlining)] bool IsBlack(Node n) => n != null && n.isBlack; [MethodImpl(MethodImplOptions.AggressiveInlining)] void Eval(Node n) { if (n == null || ei.Equals(n.lazy)) return; n.val = h(n.val, n.lazy); if (!n.needRecalc) n.dat = g(n.dat, n.lazy, n.subtreeL, n.subtreeR); if (n.left != null) n.left.lazy = h(n.left.lazy, n.lazy); if (n.right != null) n.right.lazy = h(n.right.lazy, n.lazy); n.lazy = ei; } void Recalc(Node n) { Eval(n); if (!n.needRecalc) return; n.needRecalc = false; n.dat = g(ti, n.val, n.nodeL, n.nodeR); if (n.left != null) { Recalc(n.left); n.dat = f(n.left.dat, n.dat); } if (n.right != null) { Recalc(n.right); n.dat = f(n.dat, n.right.dat); } } [MethodImpl(MethodImplOptions.AggressiveInlining)] Node RotateL(Node n) { if (n != null) { Eval(n); Eval(n.right); } Node m = n.right, t = m.left; m.left = n; n.right = t; n.subtreeR = t?.subtreeR ?? n.nodeR; m.subtreeL = n.subtreeL; n.needRecalc = true; m.needRecalc = true; return m; } [MethodImpl(MethodImplOptions.AggressiveInlining)] Node RotateR(Node n) { if (n != null) { Eval(n); Eval(n.left); } Node m = n.left, t = m.right; m.right = n; n.left = t; n.subtreeL = t?.subtreeL ?? n.nodeL; m.subtreeR = n.subtreeR; n.needRecalc = true; m.needRecalc = true; return m; } Node RotateLR(Node n) { n.left = RotateL(n.left); return RotateR(n); } Node RotateRL(Node n) { n.right = RotateR(n.right); return RotateL(n); } [MethodImpl(MethodImplOptions.AggressiveInlining)] void Add(long l, long r, E val) { root = Add(root, l, r, val); root.isBlack = true; } Node Add(Node n, long l, long r, E val) { if (n == null) { isNeedFix = true; Node ret; if (poolLength == 0) ret = new Node() { nodeL = l, subtreeL = l, nodeR = r, subtreeR = r, val = val, dat = g(ti, val, l, r), lazy = ei }; else { ret = pool[--poolLength]; ret.nodeL = l; ret.subtreeL = l; ret.nodeR = r; ret.subtreeR = r; ret.val = val; ret.dat = g(ti, val, l, r); ret.lazy = ei; ret.isBlack = false; ret.needRecalc = false; ret.left = ret.right = null; } return ret; } Eval(n); if (l < n.nodeL) n.left = Add(n.left, l, r, val); else n.right = Add(n.right, l, r, val); n.subtreeR = n.right?.subtreeR ?? n.nodeR; n.subtreeL = n.left?.subtreeL ?? n.nodeL; n.needRecalc = true; return Balance(n); } [MethodImpl(MethodImplOptions.AggressiveInlining)] Node Balance(Node n) { if (!isNeedFix || !IsBlack(n)) return n; if (IsRed(n.left) && IsRed(n.left.left)) { n = RotateR(n); n.left.isBlack = true; } else if (IsRed(n.left) && IsRed(n.left.right)) { n = RotateLR(n); n.left.isBlack = true; } else if (IsRed(n.right) && IsRed(n.right.left)) { n = RotateRL(n); n.right.isBlack = true; } else if (IsRed(n.right) && IsRed(n.right.right)) { n = RotateL(n); n.right.isBlack = true; } else isNeedFix = false; return n; } [MethodImpl(MethodImplOptions.AggressiveInlining)] void Remove(long l) { root = Remove(root, l); if (root != null) root.isBlack = true; } Node Remove(Node n, long l) { Eval(n); if (l < n.nodeL) { n.left = Remove(n.left, l); n.needRecalc = true; return BalanceL(n); } if (l > n.nodeL) { n.right = Remove(n.right, l); n.needRecalc = true; return BalanceR(n); } if (n.left == null) { isNeedFix = n.isBlack; return n.right; } n.left = RemoveMax(n.left); n.nodeL = lmax.nodeL; n.nodeR = lmax.nodeR; n.val = lmax.val; n.lazy = ei; n.needRecalc = true; pool[poolLength++] = lmax; if (pool.Length == poolLength) { var tmp = new Node[pool.Length << 1]; for (var i = 0; i < pool.Length; ++i) tmp[i] = pool[i]; pool = tmp; } return BalanceL(n); } Node RemoveMax(Node n) { Eval(n); if (n.right != null) { n.right = RemoveMax(n.right); n.subtreeR = n.right?.subtreeR ?? n.nodeR; n.needRecalc = true; return BalanceR(n); } lmax = n; isNeedFix = n.isBlack; return n.left; } Node BalanceL(Node n) { if (!isNeedFix) return n; if (IsBlack(n.right) && IsRed(n.right.left)) { var b = n.isBlack; n = RotateRL(n); n.isBlack = b; n.left.isBlack = true; isNeedFix = false; } else if (IsBlack(n.right) && IsRed(n.right.right)) { var b = n.isBlack; n = RotateL(n); n.isBlack = b; n.right.isBlack = true; n.left.isBlack = true; isNeedFix = false; } else if (IsBlack(n.right)) { isNeedFix = n.isBlack; n.isBlack = true; n.right.isBlack = false; } else { n = RotateL(n); n.isBlack = true; n.left.isBlack = false; n.left = BalanceL(n.left); isNeedFix = false; } return n; } Node BalanceR(Node n) { if (!isNeedFix) return n; if (IsBlack(n.left) && IsRed(n.left.right)) { var b = n.isBlack; n = RotateLR(n); n.isBlack = b; n.right.isBlack = true; isNeedFix = false; } else if (IsBlack(n.left) && IsRed(n.left.left)) { var b = n.isBlack; n = RotateR(n); n.isBlack = b; n.left.isBlack = true; n.right.isBlack = true; isNeedFix = false; } else if (IsBlack(n.left)) { isNeedFix = n.isBlack; n.isBlack = true; n.left.isBlack = false; } else { n = RotateR(n); n.isBlack = true; n.right.isBlack = false; n.right = BalanceR(n.right); isNeedFix = false; } return n; } List<long> removeList; [MethodImpl(MethodImplOptions.AggressiveInlining)] public void ForceUpdate(long l, long r, E val) { if (r <= l) return; removeList = new List<long>(); cnt = 0; GetRemoveKeyList(root, l, r); if (cnt > 0) Add(l1, r1, val1); foreach (var key in removeList) Remove(key); Add(l, r, val); } void GetRemoveKeyList(Node n, long l, long r) { if (r <= l) return; while (n != null) { Eval(n); n.needRecalc = true; if (r <= n.nodeL) n = n.left; else if (n.nodeR <= l) n = n.right; else break; } if (n == null) return; if (l < n.nodeL) GetRemoveKeyList(n.left, l, n.nodeL); if (n.nodeR < r) GetRemoveKeyList(n.right, n.nodeR, r); l = Max(l, n.nodeL); r = Min(r, n.nodeR); if (n.nodeL == l && r == n.nodeR) { removeList.Add(n.nodeL); } else if (n.nodeL < l && r == n.nodeR) { n.nodeR = l; } else if (n.nodeL == l && r < n.nodeR) { cnt = 1; l1 = r; r1 = n.nodeR; val1 = n.val; removeList.Add(n.nodeL); } else if (n.nodeL < l && r < n.nodeR) { cnt = 1; l1 = r; r1 = n.nodeR; val1 = n.val; n.nodeR = l; } } [MethodImpl(MethodImplOptions.AggressiveInlining)] public void Update(long l, long r, E val) { if (r <= l) return; if (l < MinKey) MinKey = l; if (MaxKey < r) MaxKey = r; if (root == null) Add(l, r, val); else if (r < root.subtreeL) { Add(r, root.subtreeL, ei); Add(l, r, val); } else if (r == root.subtreeL) { Add(l, r, val); } else if (root.subtreeR == l) { Add(l, r, val); } else if (root.subtreeR < l) { Add(root.subtreeR, l, ei); Add(l, r, val); } else { cnt = 0; Update(root, l, r, val); if (cnt > 0) Add(l1, r1, val1); if (cnt > 1) Add(l2, r2, val2); } } long l1; long r1; E val1; long l2; long r2; E val2; long cnt; void Update(Node n, long l, long r, E val) { if (r <= l) return; while (n != null) { Eval(n); n.needRecalc = true; if (r <= n.nodeL) n = n.left; else if (n.nodeR <= l) n = n.right; else break; } if (n == null) { if (++cnt == 1) { l1 = l; r1 = r; val1 = val; } else { l2 = l; r2 = r; val2 = val; } return; } if (l == n.subtreeL && r == n.subtreeR) n.lazy = val; else { if (l < n.nodeL) Update(n.left, l, n.nodeL, val); if (n.nodeR < r) Update(n.right, n.nodeR, r, val); l = Max(l, n.nodeL); r = Min(r, n.nodeR); if (n.nodeL == l && r == n.nodeR) { n.val = h(n.val, val); } else if (n.nodeL < l && r == n.nodeR) { if (++cnt == 1) { l1 = l; r1 = r; val1 = h(n.val, val); } else { l2 = l; r2 = r; val2 = h(n.val, val); } n.nodeR = l; } else if (n.nodeL == l && r < n.nodeR) { if (++cnt == 1) { l1 = r; r1 = n.nodeR; val1 = n.val; } else { l2 = r; r2 = n.nodeR; val2 = n.val; } n.val = h(n.val, val); n.nodeR = r; } else if (n.nodeL < l && r < n.nodeR) { l1 = r; r1 = n.nodeR; val1 = n.val; l2 = l; r2 = r; val2 = h(n.val, val); cnt = 2; n.nodeR = l; } } } [MethodImpl(MethodImplOptions.AggressiveInlining)] public T Query(long l, long r) { if (root == null) return ti; return Query(root, l, r); } T Query(Node n, long l, long r) { if (r <= l) return ti; while (n != null) { Recalc(n); if (r <= n.nodeL) n = n.left; else if (n.nodeR <= l) n = n.right; else break; } if (n == null) return ti; if (l == n.subtreeL && r == n.subtreeR) { return n.dat; } else { var v1 = l >= n.nodeL ? ti : Query(n.left, l, n.nodeL); var v3 = n.nodeR >= r ? ti : Query(n.right, n.nodeR, r); l = Max(l, n.nodeL); r = Min(r, n.nodeR); var v2 = g(ti, n.val, l, r); return f(f(v1, v2), v3); } } } class LIB_FastIO { [MethodImpl(MethodImplOptions.AggressiveInlining)] public LIB_FastIO() { str = Console.OpenStandardInput(); } readonly Stream str; readonly byte[] buf = new byte[2048]; int len, ptr; [MethodImpl(MethodImplOptions.AggressiveInlining)] byte read() { if (ptr >= len) { ptr = 0; if ((len = str.Read(buf, 0, 2048)) <= 0) { return 0; } } return buf[ptr++]; } [MethodImpl(MethodImplOptions.AggressiveInlining)] char Char() { byte b = 0; do b = read(); while (b < 33 || 126 < b); return (char)b; } [MethodImpl(MethodImplOptions.AggressiveInlining)] virtual public string Scan() { var sb = new StringBuilder(); for (var b = Char(); b >= 33 && b <= 126; b = (char)read()) sb.Append(b); return sb.ToString(); } [MethodImpl(MethodImplOptions.AggressiveInlining)] virtual public long Long() { long ret = 0; byte b = 0; var ng = false; do b = read(); while (b != '-' && (b < '0' || '9' < b)); if (b == '-') { ng = true; b = read(); } for (; true; b = read()) { if (b < '0' || '9' < b) return ng ? -ret : ret; else ret = (ret << 3) + (ret << 1) + b - '0'; } } [MethodImpl(MethodImplOptions.AggressiveInlining)] virtual public double Double() { return double.Parse(Scan(), CultureInfo.InvariantCulture); } } class LIB_FastIODebug : LIB_FastIO { Queue<string> param = new Queue<string>(); [MethodImpl(MethodImplOptions.AggressiveInlining)] string NextString() { if (param.Count == 0) foreach (var item in Console.ReadLine().Split(' ')) param.Enqueue(item); return param.Dequeue(); } [MethodImpl(MethodImplOptions.AggressiveInlining)] public LIB_FastIODebug() { } [MethodImpl(MethodImplOptions.AggressiveInlining)] public override string Scan() => NextString(); [MethodImpl(MethodImplOptions.AggressiveInlining)] public override long Long() => long.Parse(NextString()); [MethodImpl(MethodImplOptions.AggressiveInlining)] public override double Double() => double.Parse(NextString()); } }