#190381 (C#(csc)) No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ

• 問題: No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
• ユーザー: くれちー
• 提出日時: 2017-07-20 18:48:45
• 言語: C#(csc) (csc 3.9.0)
• 結果: WA
• 実行時間: -
• コード長: 6,646 bytes
• コンパイル時間: 2,970 ms
• コンパイル使用メモリ: 119,112 KB
• 実行使用メモリ: 53,124 KB
• 最終ジャッジ日時: 2024-10-08 17:50:49
• 合計ジャッジ時間: 8,523 ms
• ジャッジサーバーID （参考情報）: judge3 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	30 ms; 27,440 KB
testcase_01	AC	30 ms; 23,476 KB
testcase_02	AC	30 ms; 27,456 KB
testcase_03	AC	30 ms; 25,520 KB
testcase_04	AC	30 ms; 25,448 KB
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	TLE	-
testcase_10	--	-
testcase_11	--	-
testcase_12	--	-
testcase_13	--	-
testcase_14	--	-
testcase_15	--	-
testcase_16	--	-
testcase_17	--	-
testcase_18	--	-
testcase_19	--	-

コンパイルメッセージ

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;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Text;
using static System.Console;
using static System.Convert;
using static System.Math;
using static Extentions;

class IO
{
    int idx;
    string[] input;

    public IO(TextReader reader)
    {
        input = reader.ReadToEnd().Split(new[] { " ", Environment.NewLine },
            StringSplitOptions.RemoveEmptyEntries);
    }

    T Get<T>(Func<string, T> parser) => parser(input[idx++]);

    public string S => Get(s => s);
    public char C => Get(char.Parse);
    public int I => Get(int.Parse);
    public long L => Get(long.Parse);
    public double F => Get(double.Parse);
    public decimal D => Get(decimal.Parse);
    public BigInteger B => Get(BigInteger.Parse);

    T[] Gets<T>(int n, Func<string, T> parser)
        => input.Skip((idx += n) - n).Take(n).Select(parser).ToArray();

    public string[] Ss(int n) => Gets(n, s => s);
    public char[] Cs(int n) => Gets(n, char.Parse);
    public int[] Is(int n) => Gets(n, int.Parse);
    public long[] Ls(int n) => Gets(n, long.Parse);
    public double[] Fs(int n) => Gets(n, double.Parse);
    public decimal[] Ds(int n) => Gets(n, decimal.Parse);
    public BigInteger[] Bs(int n) => Gets(n, BigInteger.Parse);

    public void Write<T>(params T[] xs) => WriteLine(string.Join(" ", xs));
    public void Write(params object[] xs) => WriteLine(string.Join(" ", xs));
}

class Splarraay
{
    bool?[] array;
    bool?[] buckets;
    int bucketSize;
    int lastBucketSize;

    public long AScore { get; set; }
    public long BScore { get; set; }
    public const bool AColor = true;
    public const bool BColor = false;

    public Splarraay(int n)
    {
        array = new bool?[n];
        bucketSize = (int)Ceiling(Sqrt(n));
        buckets = new bool?[DivCeil(n, bucketSize)];
        lastBucketSize = n - bucketSize * (buckets.Length - 1);
    }

    public void Spray(bool color, int l, int r)
    {
        foreach (var bucketIdx in GetCoveredBucketIndexes(l, r))
        {
            buckets[bucketIdx] = color;
        }

        foreach (var arrayIdx in GetOverflowedArrayIndexes(l, r))
        {
            var bucketIdx = GetBucketIndexFromArrayIndex(arrayIdx);

            if (buckets[bucketIdx].HasValue)
            {
                foreach (var arrayIdx2 in GetArrayIndexesFromBucketIndex(bucketIdx))
                {
                    array[arrayIdx2] = buckets[bucketIdx].Value;
                }

                buckets[bucketIdx] = null;
            }

            array[arrayIdx] = color;
        }
    }

    public void GiveBonus(int l, int r)
    {
        var tmpAScore = 0;
        var tmpBScore = 0;
        
        foreach (var bucketIdx in GetCoveredBucketIndexes(l, r))
        {
            if (buckets[bucketIdx].HasValue)
            {
                var tmpScore = bucketIdx == buckets.Length - 1 ?
                    lastBucketSize : bucketSize;
                if (buckets[bucketIdx] == AColor) tmpAScore += tmpScore;
                else tmpBScore += tmpScore;
                continue;
            }

            foreach (var arrayIdx in GetArrayIndexesFromBucketIndex(bucketIdx))
            {
                if (!array[arrayIdx].HasValue) continue;
                if (array[arrayIdx] == AColor) tmpAScore++;
                else tmpBScore++;
            }
        }

        foreach (var arrayIdx in GetOverflowedArrayIndexes(l, r))
        {
            if (!array[arrayIdx].HasValue) continue;
            if (array[arrayIdx] == AColor) tmpAScore++;
            else tmpBScore++;
        }

        if (tmpAScore > tmpBScore) this.AScore += tmpAScore;
        if (tmpAScore < tmpBScore) this.BScore += tmpBScore;
    }

    public void Finish()
    {
        foreach (var bucketIdx in GetCoveredBucketIndexes(0, array.Length - 1))
        {
            if (buckets[bucketIdx].HasValue)
            {
                var tmpScore = bucketIdx == buckets.Length - 1 ?
                    lastBucketSize : bucketSize;
                if (buckets[bucketIdx] == AColor) this.AScore += tmpScore;
                else this.BScore += tmpScore;
                continue;
            }

            foreach (var arrayIdx in GetArrayIndexesFromBucketIndex(bucketIdx))
            {
                if (!array[arrayIdx].HasValue) continue;
                if (array[arrayIdx] == AColor) this.AScore++;
                else this.BScore++;
            }
        }

        foreach (var arrayIdx in GetOverflowedArrayIndexes(0, array.Length - 1))
        {
            if (!array[arrayIdx].HasValue) continue;
            if (array[arrayIdx] == AColor) this.AScore++;
            else this.BScore++;
        }
    }

    IEnumerable<int> GetCoveredBucketIndexes(int l, int r)
    {
        var tl = DivCeil(l, bucketSize);
        var tr = (r + 1) / bucketSize - 1;
        if (r == array.Length - 1) tr = buckets.Length - 1;
        return Enumerable.Range(tl, Max(0, tr - tl + 1));
    }

    IEnumerable<int> GetOverflowedArrayIndexes(int l, int r)
    {
        var bucketIdxes = GetCoveredBucketIndexes(l, r);
        if (bucketIdxes.Any())
        {
            var tl = bucketIdxes.First() * bucketSize;
            var tr = (bucketIdxes.Last() + 1) * bucketSize - 1;
            if (tr >= array.Length) return Enumerable.Range(l, tl - l);
            return Enumerable.Range(l, tl - l).Concat(Enumerable.Range(r, r - tr))
                .Where(y => y < array.Length);
        }
        else return Enumerable.Range(l, r - l + 1);
    }

    IEnumerable<int> GetArrayIndexesFromBucketIndex(int x)
        => Enumerable.Range(x * bucketSize, (x + 1) * bucketSize)
            .Where(y => y < array.Length);

    int GetBucketIndexFromArrayIndex(int x) => x / bucketSize;
}

static class Extentions
{
    public static int DivCeil(int x, int y) => x / y + (x % y == 0 ? 0 : 1);
}

static class Program
{
    public static void Main()
    {
#if !DEBUG
        SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
#endif
        Solve(new IO(In));
        Out.Flush();
    }

    static void Solve(IO io)
    {
        var n = io.I;
        var q = io.I;

        var spr = new Splarraay(n);

        for (var i = 0; i < q; i++)
        {
            var x = io.I;
            var l = io.I;
            var r = io.I;

            if (x == 0) spr.GiveBonus(l, r);
            if (x == 1) spr.Spray(Splarraay.AColor, l, r);
            if (x == 2) spr.Spray(Splarraay.BColor, l, r);
        }

        spr.Finish();
        io.Write(spr.AScore, spr.BScore);
    }
}