結果
問題 | No.776 A Simple RMQ Problem |
ユーザー | EmKjp |
提出日時 | 2019-05-10 19:37:48 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 1,098 ms / 3,000 ms |
コード長 | 7,348 bytes |
コンパイル時間 | 1,445 ms |
コンパイル使用メモリ | 112,388 KB |
実行使用メモリ | 48,768 KB |
最終ジャッジ日時 | 2024-07-02 01:03:42 |
合計ジャッジ時間 | 20,174 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 32 ms
19,328 KB |
testcase_01 | AC | 33 ms
18,944 KB |
testcase_02 | AC | 124 ms
29,824 KB |
testcase_03 | AC | 368 ms
44,288 KB |
testcase_04 | AC | 486 ms
30,208 KB |
testcase_05 | AC | 744 ms
45,056 KB |
testcase_06 | AC | 239 ms
32,896 KB |
testcase_07 | AC | 479 ms
45,824 KB |
testcase_08 | AC | 601 ms
33,664 KB |
testcase_09 | AC | 214 ms
46,464 KB |
testcase_10 | AC | 357 ms
34,560 KB |
testcase_11 | AC | 591 ms
47,616 KB |
testcase_12 | AC | 752 ms
48,128 KB |
testcase_13 | AC | 764 ms
48,000 KB |
testcase_14 | AC | 766 ms
48,000 KB |
testcase_15 | AC | 762 ms
48,000 KB |
testcase_16 | AC | 754 ms
48,000 KB |
testcase_17 | AC | 1,098 ms
48,128 KB |
testcase_18 | AC | 513 ms
48,128 KB |
testcase_19 | AC | 902 ms
47,616 KB |
testcase_20 | AC | 908 ms
48,512 KB |
testcase_21 | AC | 907 ms
47,616 KB |
testcase_22 | AC | 903 ms
48,768 KB |
testcase_23 | AC | 918 ms
48,000 KB |
testcase_24 | AC | 900 ms
46,976 KB |
testcase_25 | AC | 245 ms
23,168 KB |
testcase_26 | AC | 528 ms
48,128 KB |
testcase_27 | AC | 441 ms
47,872 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.Generic; using System.Globalization; using System.IO; using System.Linq; partial class Solver { static public bool UpdateMax<T>(ref T x, T newValue) where T : IComparable<T> { if (x.CompareTo(newValue) < 0) { x = newValue; return true; } return false; } public void Run() { var N = ni(); var Q = ni(); var a = ni(N); var tree = new SegmentTreeImpl(); tree.Build(a.Select(x => new NodeValue { Left = x, Middle = x, Right = x, Sum = x }).ToArray()); for (int t = 0; t < Q; t++) { var type = ns(); if (type == "set") { var i = ni() - 1; var x = ni(); tree.Update(i, new NodeValue { Left = x, Middle = x, Right = x, Sum = x }); } else { var l1 = ni() - 1; var l2 = ni() - 1; var r1 = ni() - 1; var r2 = ni() - 1; if (r1 < l1) r1 = l1; if (r2 < l2) l2 = r2; long ans = 0; if (l2 < r1) // [l1 .. l2] < [r1 .. r2] { var left = tree.Query(l1, l2 + 1); var right = tree.Query(r1, r2 + 1); var middle = (l2 + 1 < r1) ? tree.Query(l2 + 1, r1) : default(NodeValue); ans = left.Right + middle.Sum + right.Left; } else { var m1 = r1; var m2 = l2; var left = l1 < m1 ? tree.Query(l1, m1) : default(NodeValue); var middle = (m1 < m2 + 1) ? tree.Query(m1, m2 + 1) : default(NodeValue); var right = (m2 + 1 < r2 + 1) ? tree.Query(m2 + 1, r2 + 1) : default(NodeValue); ans = long.MinValue; UpdateMax(ref ans, middle.MaxValue); UpdateMax(ref ans, left.Right + middle.Sum + right.Left); UpdateMax(ref ans, left.Right + middle.Left); UpdateMax(ref ans, middle.Right + right.Left); } cout.WriteLine(ans); } } } } public struct NodeValue { public long Left { get; set; } public long Middle { get; set; } public long Right { get; set; } public long Sum { get; set; } public long MaxValue => new[] { Left, Middle, Right }.Max(); } public class SegmentTreeImpl : SegmentTree<NodeValue> { protected override NodeValue Merge(NodeValue x, NodeValue y) { return new NodeValue { Sum = x.Sum + y.Sum, Left = Math.Max(x.Left, x.Sum + y.Left), Middle = Math.Max(Math.Max(Math.Max(Math.Max(x.Middle, y.Middle), x.Right + y.Left), x.Right), y.Left), Right = Math.Max(y.Right, y.Sum + x.Right), }; } } public abstract class SegmentTree<TNodeValue> where TNodeValue : struct { protected int N { get; private set; } protected TNodeValue?[] node; protected static int Left(int p) { return p * 2 + 1; } protected static int Right(int p) { return p * 2 + 2; } public SegmentTree() { } public void Build(IList<TNodeValue> array) { Build(array.Count, i => array[i]); } virtual public void Build(int _n, Func<int, TNodeValue> create) { N = 1; while (N < _n) N *= 2; node = new TNodeValue?[2 * N]; for (int i = 0; i < _n; i++) node[i + N - 1] = create(i); for (int i = N - 2; i >= 0; i--) node[i] = Merge(node[Left(i)], node[Right(i)]); } protected TNodeValue? Merge(TNodeValue? left, TNodeValue? right) { if (left != null && right != null) return Merge(left.Value, right.Value); if (left == null) return right; if (right == null) return left; return null; } protected abstract TNodeValue Merge(TNodeValue left, TNodeValue right); public void Update(int index, TNodeValue val) { int p = index + N - 1; node[p] = val; while (p > 0) { p = (p - 1) / 2; node[p] = Merge(node[Left(p)], node[Right(p)]); } } protected virtual TNodeValue? Query(int begin, int end, int k, int l, int r) { if (r <= begin || end <= l) return null; if (begin <= l && r <= end) return node[k]; int mid = (l + r) / 2; return Merge( Query(begin, end, Left(k), l, mid), Query(begin, end, Right(k), mid, r) ); } public TNodeValue Query(int begin, int end) { return Query(begin, end, 0, 0, N).Value; } }; // PREWRITEN CODE BEGINS FROM HERE partial class Solver : Scanner { public static void Main(string[] args) { new Solver(Console.In, Console.Out).Run(); } TextReader cin; TextWriter cout; public Solver(TextReader reader, TextWriter writer) : base(reader) { this.cin = reader; this.cout = writer; } public Solver(string input, TextWriter writer) : this(new StringReader(input), writer) { } public int ni() { return NextInt(); } public int[] ni(int n) { return NextIntArray(n); } public long nl() { return NextLong(); } public long[] nl(int n) { return NextLongArray(n); } public double nd() { return NextDouble(); } public string ns() { return Next(); } public string[] ns(int n) { return NextArray(n); } } public class Scanner { private TextReader Reader; private Queue<String> TokenQueue = new Queue<string>(); private CultureInfo ci = CultureInfo.InvariantCulture; public Scanner() : this(Console.In) { } public Scanner(TextReader reader) { this.Reader = reader; } public int NextInt() { return Int32.Parse(Next(), ci); } public long NextLong() { return Int64.Parse(Next(), ci); } public double NextDouble() { return double.Parse(Next(), ci); } public string[] NextArray(int size) { var array = new string[size]; for (int i = 0; i < size; i++) array[i] = Next(); return array; } public int[] NextIntArray(int size) { var array = new int[size]; for (int i = 0; i < size; i++) array[i] = NextInt(); return array; } public long[] NextLongArray(int size) { var array = new long[size]; for (int i = 0; i < size; i++) array[i] = NextLong(); 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 bool StockTokens() { while (true) { var line = Reader.ReadLine(); if (line == null) return false; var tokens = line.Trim().Split(" ".ToCharArray(), StringSplitOptions.RemoveEmptyEntries); if (tokens.Length == 0) continue; foreach (var token in tokens) TokenQueue.Enqueue(token); return true; } } }