結果
問題 | No.776 A Simple RMQ Problem |
ユーザー |
![]() |
提出日時 | 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 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 26 |
コンパイルメッセージ
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 HEREpartial 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;}}}