結果

問題 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;
        }
    }
}
0