結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
コンテスト
ユーザー くれちー
提出日時 2017-07-20 17:49:49
言語 C#(csc)
(csc 3.9.0)
結果
RE  
実行時間 -
コード長 6,549 bytes
コンパイル時間 1,384 ms
コンパイル使用メモリ 111,616 KB
実行使用メモリ 44,800 KB
最終ジャッジ日時 2024-10-08 17:48:18
合計ジャッジ時間 10,334 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 2 WA * 1 RE * 10 TLE * 1 -- * 3
権限があれば一括ダウンロードができます
コンパイルメッセージ
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.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 int AScore { get; set; }
    public int 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 = Min(array.Length - 1, (bucketIdxes.Last() + 1) * bucketSize - 1);
            return Enumerable.Range(l, tl - l).Concat(Enumerable.Range(r, r - tr));
        }
        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);
    }
}
0