結果
問題 | No.230 Splarraay スプラレェーイ |
ユーザー |
![]() |
提出日時 | 2015-06-19 23:15:40 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 336 ms / 5,000 ms |
コード長 | 6,737 bytes |
コンパイル時間 | 933 ms |
コンパイル使用メモリ | 108,288 KB |
実行使用メモリ | 27,264 KB |
最終ジャッジ日時 | 2024-07-07 04:16:29 |
合計ジャッジ時間 | 4,248 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System;using System.IO;using System.Collections.Generic;using System.Globalization;using System.Linq;using System.Text;public class SegmentTree {public struct Node {public int Index;public bool IsEmpty;public long Value;public long LazySet;};int n;Node[] node;static int left(int p) { return p * 2 + 1; }static int right(int p) { return p * 2 + 2; }public SegmentTree(int _n) {n = 1;while (n < _n) n *= 2;node = new Node[2 * n];}public SegmentTree(int[] A): this(A.Length) {for (int i = 0; i < A.Length; i++) {node[i + n - 1] = Create(i, A[i]);}for (int i = n - 2; i >= 0; i--) {node[i] = Merge(node[left(i)], node[right(i)]);}}Node Empty() {return new Node() { IsEmpty = true };}// CUMTOMIZE FROM HERENode Create(int index, long c) {return new Node { Index = index, Value = c };}Node Merge(Node left, Node right) {return new Node { Value = left.Value + right.Value };}#region 遅延伝搬による一括更新処理void LazyPropagation(int k, int l, int r) {if (node[k].LazySet == 0) return;node[k].Value = (r - l) * node[k].LazySet;if (k < n - 1) {node[left(k)].LazySet = node[k].LazySet;node[right(k)].LazySet = node[k].LazySet;}node[k].LazySet = 0;}void LazyUpdate(int begin, int end, int k, int l, int r, long value) {if (r <= begin || end <= l) {LazyPropagation(k, l, r);return;}if (begin <= l && r <= end) {node[k].LazySet = value;LazyPropagation(k, l, r);return;}LazyPropagation(k, l, r);int mid = (l + r) / 2;LazyUpdate(begin, end, left(k), l, mid, value);LazyUpdate(begin, end, right(k), mid, r, value);node[k] = Merge(node[left(k)], node[right(k)]);}public void LazyUpdate(int begin, int end, long value) {LazyUpdate(begin, end, 0, 0, n, value);}#endregion// CUMTOMIZE ENDpublic void Update(int index, int val) {int p = index + n - 1;node[p] = Create(index, val);while (p > 0) {p = (p - 1) / 2;node[p] = Merge(node[left(p)], node[right(p)]);}}public Node Query(int begin, int end, int k, int l, int r) {LazyPropagation(k, l, r);if (r <= begin || end <= l) return Empty();if (begin <= l && r <= end) return node[k];int mid = (l + r) / 2;Node nodeL = Query(begin, end, left(k), l, mid);Node nodeR = Query(begin, end, right(k), mid, r);if (nodeL.IsEmpty) return nodeR;if (nodeR.IsEmpty) return nodeL;return Merge(nodeL, nodeR);}public Node Query(int begin, int end) {return Query(begin, end, 0, 0, n);}};partial class Solver {public void Run() {var N = ni();var Q = ni();var tree = new SegmentTree(new int[N]);const long AColorValue = 1;const long BColorValue = 1000000;long AScore = 0;long BScore = 0;for (int i = 0; i < Q; i++) {var x = ni();var l = ni();var r = ni();if (x == 0) {var sum = tree.Query(l, r + 1).Value;var ANum = sum % BColorValue;var BNum = sum / BColorValue;if (ANum > BNum)AScore += ANum;if (ANum < BNum)BScore += BNum;} else if (x == 1) {tree.LazyUpdate(l, r + 1, AColorValue);} else {tree.LazyUpdate(l, r + 1, BColorValue);}}{var sum = tree.Query(0, N).Value;var ANum = sum % BColorValue;var BNum = sum / BColorValue;AScore += ANum;BScore += BNum;}cout.WriteLine("{0} {1}", AScore, BScore);}}// 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;}}}