結果
問題 | No.945 YKC饅頭 |
ユーザー |
![]() |
提出日時 | 2019-12-11 22:19:49 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 1,553 ms / 2,000 ms |
コード長 | 19,753 bytes |
コンパイル時間 | 1,272 ms |
コンパイル使用メモリ | 117,980 KB |
実行使用メモリ | 77,988 KB |
最終ジャッジ日時 | 2024-06-24 08:03:42 |
合計ジャッジ時間 | 30,697 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 74 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System;using System.Collections;using System.Collections.Generic;using System.Globalization;using System.IO;using System.Linq;using E = System.Linq.Enumerable;internal partial class Solver {struct Query {public int Left, Right, Id;public int Kind;}int ToIndex(string s) {if (s == "Y") return 0;if (s == "K") return 1;if (s == "C") return 2;throw new NotSupportedException();}public void Run() {var N = ni();var M = ni();var Q = new Query[M];var addEvent = E.Range(0, N + 1).Select(_ => new List<int>()).ToArray();var removeEvent = E.Range(0, N + 1).Select(_ => new List<int>()).ToArray();for (int i = 0; i < M; i++) {var query = new Query {Id = i,Left = ni() - 1,Right = ni() - 1,Kind = ToIndex(ns()),};Q[i] = query;addEvent[query.Left].Add(i);removeEvent[query.Right + 1].Add(i);}var set = new MultiSet<Query>((q1, q2) => q1.Id.CompareTo(q2.Id));var ans = new int[3];for (int i = 0; i < N; i++) {foreach (var e in removeEvent[i]) {set.Remove(Q[e]);}foreach (var e in addEvent[i]) {set.Add(Q[e]);}if (set.Count > 0) {var min = set.Min();ans[min.Kind]++;}}cout.WriteLine(string.Join(" ", ans));}}public partial class Set<T> : MultiSet<T> {protected override bool AllowMultiple {get {return false;}}}public partial class MultiSet<T> {private readonly LLRBTreeNode<T> end = new LLRBTreeNode<T>(default(T));private LLRBTreeNode<T> root = null;private readonly IComparer<T> _comparer;public MultiSet() : this(Comparer<T>.Default) {}public MultiSet(IComparer<T> comparer) {_comparer = comparer;root = end;}public MultiSet(Comparison<T> comp) : this(Comparer<T>.Create(comp)) { }protected virtual bool AllowMultiple { get { return true; } }public int Count { get { return root == null ? 0 : root.Count + root.LeftTotalCount + root.RightTotalCount - 1; } }private LLRBTreeNode<T> FindNode(T value) {var node = root;while (node != null) {int cmp = Compare(value, node);if (cmp == 0) {return node;}node = (cmp < 0) ? node.Left : node.Right;}return null;}public void Clear() {root = end;}public bool Contains(T value) {var node = FindNode(value);return node != null;}public int CountOf(T value) {var node = FindNode(value);return node != null ? node.Count : 0;}public int IndexOfLowerBound(T value) {var node = root;int index = 0;while (node != null) {int cmp = Compare(value, node);if (cmp <= 0) {node = node.Left;} else {index += node.LeftTotalCount + node.Count;node = node.Right;}}return index;}private int Compare(T value, LLRBTreeNode<T> node) {if (node == end) {return -1;}return _comparer.Compare(value, node.Value);}public int IndexOfUpperBound(T value) {var node = root;int index = 0;while (node != null) {int cmp = Compare(value, node);if (cmp < 0) {node = node.Left;} else {index += node.LeftTotalCount + node.Count;node = node.Right;}}return index;}public T At(int index) {var node = root;while (node != null) {int leftCount = node.LeftTotalCount;if (leftCount <= index && index < leftCount + node.Count) {return node.Value;}if (index < leftCount) {node = node.Left;} else {index -= leftCount + node.Count;node = node.Right;}}throw new ArgumentOutOfRangeException("index");}public T Min() {return At(0);}public T Max() {return At(Count - 1);}public LLRBTreeIterator<T> AtIterator(int index) {var node = root;while (node != null) {int leftCount = node.LeftTotalCount;if (leftCount <= index && index < leftCount + node.Count) {return new LLRBTreeIterator<T>(node, index - leftCount);}if (index < leftCount) {node = node.Left;} else {index -= leftCount + node.Count;node = node.Right;}}throw new ArgumentOutOfRangeException("index");}public void Add(T value) {root = Add(root, value);root.Color = LLRBTreeNode<T>.BLACK;}private LLRBTreeNode<T> Add(LLRBTreeNode<T> h, T value) {if (h == null) {return new LLRBTreeNode<T>(value);}int cmp = Compare(value, h);if (cmp == 0) {if (AllowMultiple) {h.Count++;FixCount(h);}} else if (cmp <= 0) {h.Left = Add(h.Left, value);FixCount(h);} else {h.Right = Add(h.Right, value);FixCount(h);}if (IsRed(h.Right) && !IsRed(h.Left)) {h = RotateLeft(h);}if (IsRed(h.Left) && IsRed(h.Left.Left)) {h = RotateRight(h);}if (IsRed(h.Left) && IsRed(h.Right)) {ColorFlip(h);}return h;}private LLRBTreeNode<T> RemoveLeftestNode(LLRBTreeNode<T> h, out LLRBTreeNode<T> leftMost) {if (h.Left == null) {leftMost = h;return null;}if (!IsRed(h.Left) && !IsRed(h.Left.Left)) {h = MoveRedLeft(h);}h.Left = RemoveLeftestNode(h.Left, out leftMost);return FixUp(h);}private bool TryReduceCount(LLRBTreeNode<T> h, T value, out int num) {num = 0;if (h == null) {return false;}int cmp = Compare(value, h);if (cmp == 0) {num = h.Count;if (h.Count > 1) {h.Count--;FixCount(h);return true;}return false;}if (TryReduceCount((cmp < 0) ? h.Left : h.Right, value, out num)) {FixCount(h);return true;}return false;}public bool Remove(T value) {if (AllowMultiple) {int num;if (TryReduceCount(root, value, out num)) {return true;}if (num == 0) {return false;}} else {if (!Contains(value)) {return false;}}root = RemoveNode(root, value);if (root != null) {root.Color = LLRBTreeNode<T>.BLACK;}return true;}private LLRBTreeNode<T> RemoveNode(LLRBTreeNode<T> h, T value) {if (Compare(value, h) < 0) {if (h.Left == null) {throw new KeyNotFoundException("value");}if (!IsRed(h.Left) && !IsRed(h.Left.Left)) {h = MoveRedLeft(h);}h.Left = RemoveNode(h.Left, value);FixCount(h);} else {if (IsRed(h.Left)) {h = RotateRight(h);}if (h.Right == null) {if (Compare(value, h) == 0) {return null;}throw new KeyNotFoundException("value");}if (!IsRed(h.Right) && !IsRed(h.Right.Left)) {h = MoveRedRight(h);}if (Compare(value, h) == 0) {LLRBTreeNode<T> sub;h.Right = RemoveLeftestNode(h.Right, out sub);h = Substitute(h, sub);FixCount(h);} else {h.Right = RemoveNode(h.Right, value);FixCount(h);}}return FixUp(h);}private LLRBTreeNode<T> Substitute(LLRBTreeNode<T> node, LLRBTreeNode<T> sub) {sub.Parent = node.Parent;sub.Left = node.Left;sub.Right = node.Right;sub.TotalCount = node.TotalCount;sub.Color = node.Color;if (sub.Parent != null) {if (sub.Parent.Left == node) {sub.Parent.Left = sub;}if (sub.Parent.Right == node) {sub.Parent.Right = sub;}}if (sub.Left != null) {sub.Left.Parent = sub;}if (sub.Right != null) {sub.Right.Parent = sub;}return sub;}private static LLRBTreeNode<T> MoveRedLeft(LLRBTreeNode<T> h) {ColorFlip(h);if (IsRed(h.Right.Left)) {h.Right = RotateRight(h.Right);FixCount(h);h = RotateLeft(h);ColorFlip(h);}return h;}private static LLRBTreeNode<T> MoveRedRight(LLRBTreeNode<T> h) {ColorFlip(h);if (IsRed(h.Left.Left)) {h = RotateRight(h);ColorFlip(h);}return h;}private static LLRBTreeNode<T> RotateLeft(LLRBTreeNode<T> h) {var x = h.Right;h.Right = x.Left;x.Left = h;x.Color = h.Color;h.Color = LLRBTreeNode<T>.RED;FixCount(h);FixCount(x);return x;}private static LLRBTreeNode<T> RotateRight(LLRBTreeNode<T> h) {var x = h.Left;h.Left = x.Right;x.Right = h;x.Color = h.Color;h.Color = LLRBTreeNode<T>.RED;FixCount(h);FixCount(x);return x;}private static bool IsRed(LLRBTreeNode<T> h) {return h != null && h.Color == LLRBTreeNode<T>.RED;}private static void ColorFlip(LLRBTreeNode<T> h) {h.Color = !h.Color;h.Left.Color = !h.Left.Color;h.Right.Color = !h.Right.Color;}private static LLRBTreeNode<T> FixUp(LLRBTreeNode<T> h) {if (IsRed(h.Right)) {h = RotateLeft(h);}if (h.Left != null && IsRed(h.Left) && IsRed(h.Left.Left)) {h = RotateRight(h);}if (IsRed(h.Left) && IsRed(h.Right)) {ColorFlip(h);}FixCount(h);return h;}private static void FixCount(LLRBTreeNode<T> node) {node.TotalCount = node.Count + node.LeftTotalCount + node.RightTotalCount;}public void Debug() {if (root != null) {root.Debug();}}}public class LLRBTreeNode<T> {public const bool RED = true;public const bool BLACK = false;public T Value;public bool Color = RED;public LLRBTreeNode<T> Parent { get; set; }private LLRBTreeNode<T> _left;private LLRBTreeNode<T> _right;public LLRBTreeNode<T> Left {get { return _left; }set {if (_left == value) {return;}if (_left != null && _left.Parent == this) {_left.Parent = null;}_left = value;if (_left != null) {_left.Parent = this;}}}public LLRBTreeNode<T> Right {get { return _right; }set {if (_right == value) {return;}if (_right != null && _right.Parent == this) {_right.Parent = null;}_right = value;if (_right != null) {_right.Parent = this;}}}public int Count = 1;public LLRBTreeNode(T value) {Value = value;}public int TotalCount = 1;public int LeftTotalCount { get { return Left == null ? 0 : Left.TotalCount; } }public int RightTotalCount { get { return Right == null ? 0 : Right.TotalCount; } }public void Debug(string indent = "") {Console.WriteLine(indent + ":" + Value + " - " + Count + " - " + TotalCount);if (Left != null) {Left.Debug(indent + "L");}if (Right != null) {Right.Debug(indent + "R");}}}public struct LLRBTreeIterator<T> {private readonly LLRBTreeNode<T> _node;private readonly int _index;public LLRBTreeIterator(LLRBTreeNode<T> node, int index = 0) {_node = node;_index = index;}public T Value { get { return _node.Value; } }public static LLRBTreeIterator<T> operator ++(LLRBTreeIterator<T> x) {return x.GetSuccessor();}public static LLRBTreeIterator<T> operator --(LLRBTreeIterator<T> x) {return x.GetPredecessor();}private LLRBTreeIterator<T> GetSuccessor() {if (_index + 1 < _node.Count) {return new LLRBTreeIterator<T>(_node, _index + 1);} else {LLRBTreeNode<T> current, parent;if (_node.Right == null) {for (current = _node, parent = _node.Parent; parent.Right == current; current = parent, parent = current.Parent) {;}return new LLRBTreeIterator<T>(parent);} else {for (parent = _node.Right, current = parent.Left; current != null; parent = current, current = parent.Left) {;}return new LLRBTreeIterator<T>(parent);}}}private LLRBTreeIterator<T> GetPredecessor() {if (0 <= _index - 1) {return new LLRBTreeIterator<T>(_node, _index - 1);} else {LLRBTreeNode<T> current, parent;if (_node.Left == null) {for (current = _node, parent = _node.Parent; parent.Left == current; current = parent, parent = current.Parent) {;}return new LLRBTreeIterator<T>(parent, parent.Count - 1);} else {for (parent = _node.Left, current = parent.Right; current != null; parent = current, current = parent.Right) {;}return new LLRBTreeIterator<T>(parent, parent.Count - 1);}}}}public partial class MultiSet<T> : IEnumerable<T> {public IEnumerator<T> GetEnumerator() {var node = root;var stack = new Stack<LLRBTreeNode<T>>();while (node != null || stack.Count > 0) {while (node != null) {stack.Push(node);node = node.Left;}node = stack.Pop();if (node == end) {break;}int count = node.Count;for (int i = 0; i < count; i++) {yield return node.Value;}node = node.Right;}}IEnumerator IEnumerable.GetEnumerator() {return GetEnumerator();}}// PREWRITEN CODE BEGINS FROM HEREinternal partial class Solver : Scanner {public static void Main(string[] args) {#if LOCALbyte[] inputBuffer = new byte[1000000];var inputStream = Console.OpenStandardInput(inputBuffer.Length);using (var reader = new StreamReader(inputStream, Console.InputEncoding, false, inputBuffer.Length)) {Console.SetIn(reader);new Solver(Console.In, Console.Out).Run();}#elseConsole.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false });new Solver(Console.In, Console.Out).Run();Console.Out.Flush();#endif}#pragma warning disable IDE0052private readonly TextReader cin;private readonly TextWriter cout;#pragma warning restore IDE0052public Solver(TextReader reader, TextWriter writer): base(reader) {cin = reader;cout = writer;}public Solver(string input, TextWriter writer): this(new StringReader(input), writer) {}#pragma warning disable IDE1006#pragma warning disable IDE0051private int ni() { return NextInt(); }private int[] ni(int n) { return NextIntArray(n); }private long nl() { return NextLong(); }private long[] nl(int n) { return NextLongArray(n); }private double nd() { return NextDouble(); }private double[] nd(int n) { return NextDoubleArray(n); }private string ns() { return Next(); }private string[] ns(int n) { return NextArray(n); }#pragma warning restore IDE1006#pragma warning restore IDE0051}internal static class LinqPadExtension {public static T Dump<T>(this T obj) {#if LOCALreturn LINQPad.Extensions.Dump(obj);#elsereturn obj;#endif}}public class Scanner {private readonly TextReader Reader;private readonly Queue<string> TokenQueue = new Queue<string>();private readonly CultureInfo ci = CultureInfo.InvariantCulture;public Scanner(): this(Console.In) {}public Scanner(TextReader reader) {Reader = reader;}public int NextInt() { return int.Parse(Next(), ci); }public long NextLong() { return long.Parse(Next(), ci); }public double NextDouble() { return double.Parse(Next(), ci); }public string[] NextArray(int size) {string[] array = new string[size];for (int i = 0; i < size; i++) {array[i] = Next();}return array;}public int[] NextIntArray(int size) {int[] array = new int[size];for (int i = 0; i < size; i++) {array[i] = NextInt();}return array;}public long[] NextLongArray(int size) {long[] array = new long[size];for (int i = 0; i < size; i++) {array[i] = NextLong();}return array;}public double[] NextDoubleArray(int size) {double[] array = new double[size];for (int i = 0; i < size; i++) {array[i] = NextDouble();}return array;}public string Next() {if (TokenQueue.Count == 0) {if (!StockTokens()) {throw new InvalidOperationException();}}return TokenQueue.Dequeue();}public bool HasNext() {if (TokenQueue.Count > 0) {return true;}return StockTokens();}private static readonly char[] _separator = new[] { ' ', '\t' };private bool StockTokens() {while (true) {string line = Reader.ReadLine();if (line == null) {return false;}string[] tokens = line.Split(_separator, StringSplitOptions.RemoveEmptyEntries);if (tokens.Length == 0) {continue;}foreach (string token in tokens) {TokenQueue.Enqueue(token);}return true;}}}