結果

問題 No.230 Splarraay スプラレェーイ
ユーザー EmKjp
提出日時 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.

ソースコード

diff #
プレゼンテーションモードにする

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 HERE
Node 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 END
public 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 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;
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0