結果
問題 | No.1074 増殖 |
ユーザー | EmKjp |
提出日時 | 2020-06-05 22:17:46 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 400 ms / 2,000 ms |
コード長 | 16,750 bytes |
コンパイル時間 | 1,245 ms |
コンパイル使用メモリ | 118,588 KB |
実行使用メモリ | 41,892 KB |
最終ジャッジ日時 | 2024-12-17 15:56:37 |
合計ジャッジ時間 | 4,694 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 42 ms
37,644 KB |
testcase_01 | AC | 42 ms
37,764 KB |
testcase_02 | AC | 44 ms
37,648 KB |
testcase_03 | AC | 42 ms
35,728 KB |
testcase_04 | AC | 44 ms
35,712 KB |
testcase_05 | AC | 42 ms
35,720 KB |
testcase_06 | AC | 257 ms
37,812 KB |
testcase_07 | AC | 254 ms
39,976 KB |
testcase_08 | AC | 273 ms
41,628 KB |
testcase_09 | AC | 400 ms
41,892 KB |
testcase_10 | AC | 251 ms
39,844 KB |
testcase_11 | AC | 193 ms
39,956 KB |
testcase_12 | AC | 196 ms
39,716 KB |
testcase_13 | AC | 301 ms
37,668 KB |
testcase_14 | AC | 301 ms
41,888 KB |
コンパイルメッセージ
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.Diagnostics;using System.Globalization;using System.IO;using System.Text;using System.Linq;using E = System.Linq.Enumerable;internal partial class Solver {public void Run() {var n = ni();var xa = new int[n];var ya = new int[n];var xb = new int[n];var yb = new int[n];for (int i = 0; i < n; i++) {xa[i] = ni();ya[i] = ni();xb[i] = ni();yb[i] = ni();}Tuple<int, int> Get(int index, int type) {if (type == 0) {return Tuple.Create(xb[index], yb[index]);} else if (type == 1) {return Tuple.Create(-xa[index], yb[index]);} else if (type == 2) {return Tuple.Create(-xa[index], -ya[index]);} else {return Tuple.Create(xb[index], -ya[index]);}}var x = new int[n];var y = new int[n];var ans = new long[n];for (int t = 0; t < 4; t++) {for (int i = 0; i < n; i++) {var pair = Get(i, t);x[i] = pair.Item1;y[i] = pair.Item2;}var sub = Solve(n, x, y);for (int i = 0; i < n; i++) {ans[i] += sub[i];}}cout.WriteLine(ans.JoinToString("\n"));}private long[] Solve(int n, int[] x, int[] y) {var seg = new SegmentTreeBeats();seg.Build(new long[20010]);var area = 0L;var res = new long[n];for (int i = 0; i < n; i++) {seg.RangeUpdateMax(0, x[i], y[i]);var newArea = seg.QuerySum(0, 20010);//new { index = i, x = x[i], y = y[i], area, newArea }.Dump();res[i] = newArea - area;area = newArea;}return res;}}public class SegmentTreeBeats {private struct Node {public long Max, Max2nd, Min, Min2nd, Sum;public int MaxCount, MinCount;public Node(long value) {Max = Min = value;Max2nd = long.MinValue;Min2nd = long.MaxValue;MaxCount = MinCount = 1;Sum = value;}}private enum OperatorType {None = 0,Set = 1,Add = 2,}private struct Operator {public static readonly Operator None = new Operator();public OperatorType Type;public long Value;}private Node[] _node;private Operator[] _operators;private int[] _dataNum;private int N;public void Build(IList<long> array) {Build(array.Count, i => array[i]);}public void Build(int n, Func<int, long> create) {N = 1;while (N < n) {N *= 2;}_node = new Node[2 * N];_operators = new Operator[2 * N];_dataNum = new int[2 * N];for (int i = 0; i < n; i++) {_node[i + N] = new Node(create(i));_dataNum[i + N] = 1;}for (int i = n; i < N; i++) {_node[i + N] = new Node(0);}for (int i = N - 1; i > 0; i--) {_dataNum[i] = _dataNum[i << 1] + _dataNum[i << 1 | 1];BottomUp(i);}}private void BottomUp(int k) {Merge(ref _node[k], ref _node[k << 1], ref _node[k << 1 | 1]);}private static void Merge(ref Node node, ref Node child1, ref Node child2) {int cmp;cmp = child1.Max.CompareTo(child2.Max);if (cmp < 0) {node.Max = child2.Max;node.MaxCount = child2.MaxCount;node.Max2nd = Math.Max(child2.Max2nd, child1.Max);} else if (cmp > 0) {node.Max = child1.Max;node.MaxCount = child1.MaxCount;node.Max2nd = Math.Max(child1.Max2nd, child2.Max);} else {node.Max = child1.Max;node.MaxCount = child1.MaxCount + child2.MaxCount;node.Max2nd = Math.Max(child1.Max2nd, child2.Max2nd);}cmp = child1.Min.CompareTo(child2.Min);if (cmp < 0) {node.Min = child1.Min;node.MinCount = child1.MinCount;node.Min2nd = Math.Min(child1.Min2nd, child2.Min);} else if (cmp > 0) {node.Min = child2.Min;node.MinCount = child2.MinCount;node.Min2nd = Math.Min(child2.Min2nd, child1.Min);} else {node.Min = child1.Min;node.MinCount = child1.MinCount + child2.MinCount;node.Min2nd = Math.Min(child1.Min2nd, child2.Min2nd);}node.Sum = child1.Sum + child2.Sum;}private void TopDown(int k) {int c1 = k << 1;int c2 = c1 | 1;if (_operators[k].Type != OperatorType.None) {Apply(c1, ref _node[c1], _operators[k]);Apply(c2, ref _node[c2], _operators[k]);_operators[k] = Operator.None;}long kmax = _node[k].Max;long kmin = _node[k].Min;if (kmax < _node[c1].Max) { UpdateNodeMax(ref _node[c1], kmax); }if (kmax < _node[c2].Max) { UpdateNodeMax(ref _node[c2], kmax); }if (kmin > _node[c1].Min) { UpdateNodeMin(ref _node[c1], kmin); }if (kmin > _node[c2].Min) { UpdateNodeMin(ref _node[c2], kmin); }}private void Apply(int k, ref Node node, Operator @operator) {int dataNum = _dataNum[k];if (@operator.Type == OperatorType.Set) {node.Max = node.Min = @operator.Value;node.MaxCount = node.MinCount = dataNum;node.Max2nd = long.MinValue;node.Min2nd = long.MaxValue;node.Sum = dataNum * @operator.Value;} else if (@operator.Type == OperatorType.Add) {if (@operator.Value != 0) {node.Max += @operator.Value;node.Min += @operator.Value;if (node.Max2nd != long.MinValue) { node.Max2nd += @operator.Value; }if (node.Min2nd != long.MaxValue) { node.Min2nd += @operator.Value; }node.Sum += dataNum * @operator.Value;}} else {throw new Exception();}Merge(ref _operators[k], @operator);}private static void Merge(ref Operator current, Operator append) {if (current.Type != OperatorType.None) {if (append.Type == OperatorType.Set) { // add (+set +add)current = append;} else if (current.Type == OperatorType.Set) { // set add (+add)current.Value += append.Value;} else {current.Value += append.Value;}} else {current = append;}}private void ChangeApply(int begin, int end, Operator @operator) {Action<int, int, int> apply = null;apply = (k, l, r) => {if (r <= begin || end <= l) {return;}if (begin <= l && r <= end) {Apply(k, ref _node[k], @operator);return;}int mid = (l + r) >> 1;TopDown(k);apply(k << 1 | 0, l, mid);apply(k << 1 | 1, mid, r);BottomUp(k);};apply(1, 0, N);}private void ChangeApply(int begin, int end, long value, Func<int, long, bool> breakCondition, Func<int, long, bool> tagCondition, Action<int,long> tag) {Action<int, int, int> apply = null;apply = (k, l, r) => {if (r <= begin || end <= l || breakCondition(k, value)) {return;}if (begin <= l && r <= end && tagCondition(k, value)) {tag(k, value);return;}int mid = (l + r) >> 1;TopDown(k);apply(k << 1 | 0, l, mid);apply(k << 1 | 1, mid, r);BottomUp(k);};apply(1, 0, N);}private void UpdateNodeMin(int k, long value) {UpdateNodeMin(ref _node[k], value);}private static void UpdateNodeMin(ref Node node, long value) {node.Sum += (value - node.Min) * node.MinCount;if (node.Min == node.Max) {node.Min = node.Max = value;} else if (node.Min == node.Max2nd) {node.Min = node.Max2nd = value;} else {node.Min = value;}}private void UpdateNodeMax(int k, long value) {UpdateNodeMax(ref _node[k], value);}private static void UpdateNodeMax(ref Node node, long value) {node.Sum += (value - node.Max) * node.MaxCount;if (node.Max == node.Min) {node.Max = node.Min = value;} else if (node.Max == node.Min2nd) {node.Max = node.Min2nd = value;} else {node.Max = value;}}/// <summary>/// a[i] = value where i in [begin,end)/// </summary>public void RangeSet(int begin, int end, long value) {ChangeApply(begin, end, new Operator { Type = OperatorType.Set, Value = value });}/// <summary>/// a[i] += value where i in [begin,end)/// </summary>public void RangeAdd(int begin, int end, long value) {ChangeApply(begin, end, new Operator { Type = OperatorType.Add, Value = value });}/// <summary>/// a[i] = Min(a[i], value) where i in [begin,end)/// </summary>public void RangeUpdateMin(int begin, int end, long value) {ChangeApply(begin, end, value,(k, v) => _node[k].Max <= value,(k, v) => _node[k].Max2nd < value,UpdateNodeMax);}/// <summary>/// a[i] = Max(a[i], value) where i in [begin,end)/// </summary>public void RangeUpdateMax(int begin, int end, long value) {ChangeApply(begin, end, value,(k, v) => value <= _node[k].Min,(k, v) => value < _node[k].Min2nd,UpdateNodeMin);}public long QueryMin(int begin, int end) {Func<int, int, int, long> query = null;query = (k, l, r) => {if (r <= begin || end <= l) {return long.MaxValue;}if (begin <= l && r <= end) {return _node[k].Min;}int mid = (l + r) >> 1;TopDown(k);long lv = query(k << 1 | 0, l, mid);long rv = query(k << 1 | 1, mid, r);return Math.Min(lv, rv);};return query(1, 0, N);}public long QueryMax(int begin, int end) {Func<int, int, int, long> query = null;query = (k, l, r) => {if (r <= begin || end <= l) {return long.MinValue;}if (begin <= l && r <= end) {return _node[k].Max;}int mid = (l + r) >> 1;TopDown(k);long lv = query(k << 1 | 0, l, mid);long rv = query(k << 1 | 1, mid, r);return Math.Max(lv, rv);};return query(1, 0, N);}public long QuerySum(int begin, int end) {Func<int, int, int, long> query = null;query = (k, l, r) => {if (r <= begin || end <= l) {return 0;}if (begin <= l && r <= end) {return _node[k].Sum;}int mid = (l + r) >> 1;TopDown(k);long lv = query(k << 1 | 0, l, mid);long rv = query(k << 1 | 1, mid, r);return lv + rv;};return query(1, 0, N);}}// PREWRITEN CODE BEGINS FROM HEREstatic public class StringExtensions {static public string JoinToString<T>(this IEnumerable<T> source, string separator = " ") {return string.Join(separator, source);}}internal partial class Solver : Scanner {public static void Main() {#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;private readonly TextWriter cerr;#pragma warning restore IDE0052public Solver(TextReader reader, TextWriter writer): base(reader) {cin = reader;cout = writer;cerr = Console.Error;}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 {[Conditional("DEBUG")]public static void Dump<T>(this T obj) {#if DEBUGLINQPad.Extensions.Dump(obj);#endif}}public class Scanner {private readonly TextReader Reader;private readonly CultureInfo ci = CultureInfo.InvariantCulture;private readonly char[] buffer = new char[2 * 1024];private int cursor = 0, length = 0;private string Token;private readonly StringBuilder sb = new StringBuilder(1024);public Scanner(): this(Console.In) {}public Scanner(TextReader reader) {Reader = reader;}public int NextInt() { return checked((int)NextLong()); }public long NextLong() {var s = Next();long r = 0;int i = 0;bool negative = false;if (s[i] == '-') {negative = true;i++;}for (; i < s.Length; i++) {r = r * 10 + (s[i] - '0');#if DEBUGif (!char.IsDigit(s[i])) throw new FormatException();#endif}return negative ? -r : r;}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 (Token == null) {if (!StockToken()) {throw new Exception();}}var token = Token;Token = null;return token;}public bool HasNext() {if (Token != null) {return true;}return StockToken();}private bool StockToken() {while (true) {sb.Clear();while (true) {if (cursor >= length) {cursor = 0;if ((length = Reader.Read(buffer, 0, buffer.Length)) <= 0) {break;}}var c = buffer[cursor++];if (33 <= c && c <= 126) {sb.Append(c);} else {if (sb.Length > 0) break;}}if (sb.Length > 0) {Token = sb.ToString();return true;}return false;}}}