#393917 (C#(csc)) No.919 You Are A Project Manager

• 問題: No.919 You Are A Project Manager
• ユーザー: EmKjp
• 提出日時: 2019-10-26 09:52:59
• 言語: C#(csc) (csc 3.9.0)
• 結果: AC
• 実行時間: 249 ms / 3,000 ms
• コード長: 19,874 bytes
• コンパイル時間: 4,909 ms
• コンパイル使用メモリ: 111,616 KB
• 実行使用メモリ: 38,368 KB
• 最終ジャッジ日時: 2024-06-27 18:02:51
• 合計ジャッジ時間: 9,913 ms
• ジャッジサーバーID （参考情報）: judge1 / judge2

ファイルパターン	結果
sample	AC * 3
other	AC * 55

コンパイルメッセージ

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.Generic;
using System.Globalization;
using System.IO;
using System.Linq;

using E = System.Linq.Enumerable;

internal partial class Solver {
    public void Run() {
        var n = ni();
        var a = ni(n);

        var d = IndexDictionaryFactory.Create(a);

        var tree = new WaveletTree(n + 10000);
        for (int i = 0; i < n; i++) {
            tree.Add(d.GetIndex(a[i]));
        }

        long ans = 0;
        for (int k = 1; k <= n; k++) {
            ans = Math.Max(ans, Solve(tree, d, k));
        }

        cout.WriteLine(ans);
    }

    private static long Solve(WaveletTree tree, IndexDictionary<int> d, int k) {
        int n = tree.Length;
        var left = new List<long>();
        var right = new List<long>();
        var median = (k - 1) / 2;
        for (int i = 0; i + k - 1 < n; i += k) {
            left.Add(1L * k * d[tree.Quantile(i, i + k, median + 1)]);
        }
        for (int i = n - k; i >= 0; i -= k) {
            right.Add(1L * k * d[tree.Quantile(i, i + k, median + 1)]);
        }
        for (int i = 0; i < left.Count; i++) {
            if (i - 1 >= 0) left[i] += left[i - 1];
            if (i - 1 >= 0) right[i] += right[i - 1];
        }
        for (int i = 0; i < left.Count; i++) {
            if (i - 1 >= 0 && left[i - 1] > left[i]) left[i] = left[i - 1];
            if (i - 1 >= 0 && right[i - 1] > right[i]) right[i] = right[i - 1];
        }
        long ans = 0;

        var t = n / k;
        for (int i = 0; i <= t; i++) {
            var sub = 0L;
            var takeLeft = i;
            var takeRight = t - i;
            if (takeLeft > 0) sub += left[takeLeft - 1];
            if (takeRight > 0) sub += right[takeRight - 1];
            ans = Math.Max(ans, sub);
        }
        return ans;
    }
}
public class IndexDictionary<T> {
    private readonly Dictionary<T, int> _toIndex;
    private readonly T[] _array;

    public IndexDictionary(IEnumerable<T> source) : this(source, Comparer<T>.Default) { }

    public IndexDictionary(IEnumerable<T> source, IComparer<T> comparer) {
        _array = source.Distinct().ToArray();
        Array.Sort(_array, comparer);
        _toIndex = new Dictionary<T, int>(_array.Length);
        int index = -1;
        foreach (var x in _array) {
            _toIndex[x] = ++index;
        }
    }

    public int Count { get { return _array.Length; } }

    public T this[int index] { get { return _array[index]; } }

    public int GetIndex(T value) { return _toIndex[value]; }
}

public class IndexDictionaryFactory {
    public static IndexDictionary<T> Create<T>(IEnumerable<T> source) {
        return new IndexDictionary<T>(source);
    }
}


public class WaveletTree {
    private class BitArray {
        private const int BlockBitCount = 64;

        private readonly List<int> rankTable = new List<int>();
        private readonly List<ulong> bitBlocks;
        private int oneNum;

        private static int PopCount(ulong x) {
            x = (x & 0x5555555555555555UL) + ((x >> 1) & 0x5555555555555555UL);
            x = (x & 0x3333333333333333UL) + ((x >> 2) & 0x3333333333333333UL);
            x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0fUL;
            x = x + (x >> 8);
            x = x + (x >> 16);
            x = x + (x >> 32);
            return (int)(x & 0x7FLU);
        }

        private static int PopCountWithMask(ulong x, int offset) {
            if (offset == 0) {
                return 0;
            }

            return PopCount(x & ((1LU << offset) - 1));
        }

        public BitArray(int n = 0) {
            Count = n;
            oneNum = 0;
            int blockNum = (Count + BlockBitCount - 1) / BlockBitCount;
            bitBlocks = new List<ulong>(blockNum);
            for (int i = 0; i < blockNum; i++) {
                bitBlocks.Add(0);
            }
        }

        public int Count { get; private set; }

        public void Add(bool bit) {
            Count++;
            int last = Count - 1;
            if (last / BlockBitCount == bitBlocks.Count) {
                bitBlocks.Add(0UL);
                int table_num = bitBlocks.Count + 1;
                while (rankTable.Count < table_num) {
                    rankTable.Add(rankTable.Count > 0 ? rankTable[rankTable.Count - 1] : 0);
                }
            }
            SetBit(bit, last);
            if (bit) {
                rankTable[rankTable.Count - 1]++;
                oneNum++;
            }
        }

        public void RemoveBack() {
            int last = Count - 1;
            if (Get(last)) {
                oneNum--;
                rankTable[rankTable.Count - 1]--;
            }
            SetBit(false, last);
            last--;
            if (last / BlockBitCount + 1 < bitBlocks.Count) {
                bitBlocks.RemoveAt(bitBlocks.Count - 1);
                int table_num = bitBlocks.Count + 1;
                while (rankTable.Count > table_num) {
                    rankTable.RemoveAt(rankTable.Count - 1);
                }
            }
            Count--;
        }

        public void Build() {
            int table_num = bitBlocks.Count + 1;
            for (int i = 0; i < table_num; i++) {
                rankTable.Add(0);
            }

            oneNum = 0;
            for (int i = 0; i < bitBlocks.Count; i++) {
                rankTable[i] = oneNum;
                oneNum += PopCount(bitBlocks[i]);
            }
            rankTable[rankTable.Count - 1] = oneNum;
        }

        public void SetBit(bool bit, int pos) {
            if (bit) {
                bitBlocks[pos / BlockBitCount] |= (1LU << (pos % BlockBitCount));
            } else {
                bitBlocks[pos / BlockBitCount] &= ~(1LU << (pos % BlockBitCount));
            }
        }

        public int Rank(int pos) {
            int blockIndex = pos / BlockBitCount;
            int rank = rankTable[blockIndex];
            if (blockIndex < bitBlocks.Count) {
                rank += PopCountWithMask(bitBlocks[blockIndex], pos % BlockBitCount);
            }
            return rank;
        }

        public int Rank(bool bit, int pos) {
            return bit ? Rank(pos) : pos - Rank(pos);
        }
        public void Rank(int pos, out int rank0, out int rank1) {
            rank1 = Rank(pos);
            rank0 = pos - rank1;
        }

        public int Select(bool bit, int rank) {
            int blockPos = SelectOutBlock(bit, ref rank);
            ulong blockBit = bitBlocks[blockPos];
            if (!bit) {
                blockBit = ~blockBit;
            }

            return blockPos * BlockBitCount + SelectInBlock(blockBit, rank);
        }

        public bool Get(int pos) {
            return ((bitBlocks[pos / BlockBitCount] >> (pos % BlockBitCount)) & 1) != 0;
        }

        public int GetOneNum() {
            return oneNum;
        }

        public int GetZeroNum() {
            return Count - oneNum;
        }

        private int SelectOutBlock(bool bit, ref int rank) {
            int left = 0, right = rankTable.Count - 1;
            int tableIndex = 0;
            while (left <= right) {
                int mid = (left + right) / 2;
                int bitLength = (BlockBitCount * mid);
                int bitNum = bit ? rankTable[mid] : bitLength - rankTable[mid];
                if (bitNum < rank) {
                    tableIndex = mid;
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            int blockPos = tableIndex;
            rank -= bit ? rankTable[tableIndex] : blockPos * BlockBitCount - rankTable[tableIndex];

            for (; blockPos < bitBlocks.Count; blockPos++) {
                int nextRank = bit ? PopCount(bitBlocks[blockPos]) : BlockBitCount - PopCount(bitBlocks[blockPos]);
                if (rank <= nextRank) {
                    break;
                }

                rank -= nextRank;
            }
            return blockPos;
        }

        private int SelectInBlock(ulong x, int rank) {
            ulong x1 = x - ((x & 0xAAAAAAAAAAAAAAAALU) >> 1);
            ulong x2 = (x1 & 0x3333333333333333LU) + ((x1 >> 2) & 0x3333333333333333LU);
            ulong x3 = (x2 + (x2 >> 4)) & 0x0F0F0F0F0F0F0F0FLU;

            int pos = 0;
            for (; ; pos += 8) {
                int rank_next = (int)((x3 >> pos) & 0xFFLU);
                if (rank <= rank_next) {
                    break;
                }

                rank -= rank_next;
            }

            int v2 = (int)((x2 >> pos) & 0xFL); if (rank > v2) { rank -= v2; pos += 4; }
            int v1 = (int)((x1 >> pos) & 0x3L); if (rank > v1) { rank -= v1; pos += 2; }
            int v0 = (int)((x >> pos) & 0x1L); if (rank > v0) { rank -= v0; pos += 1; }

            return pos;
        }
    };
    private readonly int BitNum;
    public int Length { get; private set; }

    private readonly BitArray[] bitArray;

    private int Left(int x) { return x * 2 + 1; }

    private int Right(int x) { return x * 2 + 2; }

    public WaveletTree(int maxValue) {
        BitNum = 1;
        while ((1 << BitNum) < maxValue) {
            BitNum++;
        }

        bitArray = new BitArray[1 << (BitNum + 1)];
    }

    public void Init(int[] array) {
        Length = array.Length;
        Init(0, BitNum - 1, array);
    }

    private void Init(int index, int bitPos, IList<int> array) {
        if (array.Count == 0) {
            return;
        }

        var b = GetBitArrayOrCreate(index, array.Count);
        var zero = new List<int>();
        var one = new List<int>();
        for (int i = 0; i < array.Count; i++) {
            if ((array[i] & (1 << bitPos)) != 0) {
                one.Add(array[i]);
                b.SetBit(true, i);
            } else {
                zero.Add(array[i]);
                b.SetBit(false, i);
            }
        }
        b.Build();

        if (bitPos - 1 >= 0) {
            Init(Left(index), bitPos - 1, zero);
            Init(Right(index), bitPos - 1, one);
        }
    }

    private BitArray GetBitArrayOrCreate(int index, int n = 0) {
        return bitArray[index] ?? (bitArray[index] = new BitArray(n));
    }

    public int Access(int k) {
        return Access(k, 0, BitNum - 1);
    }

    private int Access(int k, int index, int bitPos) {
        if (bitPos < 0) {
            return 0;
        }

        var b = bitArray[index];
        if (b == null || b.Count == 0) {
            return 0;
        }

        if (b.Get(k)) {
            return Access(b.Rank(true, k), Right(index), bitPos - 1) | (1 << bitPos);
        } else {
            return Access(b.Rank(false, k), Left(index), bitPos - 1);
        }
    }

    public void Add(int x) {
        Add(x, 0, BitNum - 1);
        Length++;
    }

    private void Add(int x, int index, int bitPos) {
        if (bitPos < 0) {
            return;
        }

        var b = GetBitArrayOrCreate(index);
        bool bit = (x & (1 << bitPos)) != 0;
        b.Add(bit);
        Add(x, bit ? Right(index) : Left(index), bitPos - 1);
    }

    public void RemoveBack() {
        RemoveBack(0, BitNum - 1);
        Length--;
    }

    private void RemoveBack(int index, int bitPos) {
        if (bitPos < 0) {
            return;
        }

        var b = GetBitArrayOrCreate(index);
        bool bit = b.Get(b.Count - 1);
        b.RemoveBack();
        if (bit) {
            RemoveBack(Right(index), bitPos - 1);
        } else {
            RemoveBack(Left(index), bitPos - 1);
        }
    }

    public void RankAll(int c, int pos, out int rank, out int rankLessThan, out int rankMoreThan) {
        rankLessThan = 0;
        rankMoreThan = 0;
        RankAll(c, pos, 0, BitNum - 1, ref rankLessThan, ref rankMoreThan);
        rank = pos - rankMoreThan - rankLessThan;
    }

    private void RankAll(int c, int pos, int index, int bitPos, ref int rankLessThan, ref int rankMoreThan) {
        if (bitPos < 0) {
            return;
        }

        var b = bitArray[index];
        if (b == null || b.Count == 0) {
            return;
        }

        int pos0Num, pos1Num;
        b.Rank(pos, out pos0Num, out pos1Num);
        if ((c & (1 << bitPos)) != 0) {
            rankLessThan += pos0Num;
            RankAll(c, pos1Num, Right(index), bitPos - 1, ref rankLessThan, ref rankMoreThan);
        } else {
            rankMoreThan += pos1Num;
            RankAll(c, pos0Num, Left(index), bitPos - 1, ref rankLessThan, ref rankMoreThan);
        }
    }

    /// <summary>
    /// return the number of occurrences of c in [0,pos)
    /// </summary>
    public int Rank(int c, int pos) {
        int rank, more, less;
        RankAll(c, pos, out rank, out less, out more);
        return rank;
    }

    public int RankMoreThan(int c, int pos) {
        int rank, more, less;
        RankAll(c, pos, out rank, out less, out more);
        return more;
    }

    public int RankLessThan(int c, int pos) {
        int rank, more, less;
        RankAll(c, pos, out rank, out less, out more);
        return less;
    }

    /// <summary>
    /// return min value in [begin,end)
    /// </summary>
    public int MinRange(int begin, int end) {
        return Quantile(begin, end, 1);
    }

    /// <summary>
    /// return max value in [begin,end)
    /// </summary>
    public int MaxRange(int begin, int end) {
        return Quantile(begin, end, end - begin);
    }

    /// <summary>
    /// return k-th value in [begin,end)
    /// k is 1-index
    /// </summary>
    public int Quantile(int begin, int end, int k) {
        return Quantile(begin, end, k, 0, BitNum - 1);
    }

    private int Quantile(int begin, int end, int k, int index, int bitPos) {
        if (bitPos < 0) {
            return 0;
        }

        var b = bitArray[index];
        if (b == null || b.Count == 0) {
            return 0;
        }

        int begin0Num, begin1Num, end0Num, end1Num;
        b.Rank(begin, out begin0Num, out begin1Num);
        b.Rank(end, out end0Num, out end1Num);
        int range0Num = end0Num - begin0Num;
        if (k <= range0Num) {
            return Quantile(begin0Num, end0Num, k, Left(index), bitPos - 1);
        } else {
            return Quantile(begin1Num, end1Num, k - range0Num, Right(index), bitPos - 1) | (1 << bitPos);
        }
    }

    public int FreqRange(int begin, int end, int minValue, int maxValue) // [min,max)
    {
        if (minValue >= maxValue) {
            return 0;
        }

        if (begin >= end) {
            return 0;
        }

        return RankLessThan(maxValue, end) - RankLessThan(minValue, end)
            - RankLessThan(maxValue, begin) + RankLessThan(minValue, begin);
    }


    public int XorMax(int begin, int end, int x) {
        return XorMax(begin, end, x, 0, BitNum - 1);
    }

    private int XorMax(int begin, int end, int x, int index, int bitPos) {
        if (bitPos < 0) {
            return 0;
        }

        var b = bitArray[index];
        if (b == null || b.Count == 0) {
            return 0;
        }

        int begin0Num, begin1Num, end0Num, end1Num;
        b.Rank(begin, out begin0Num, out begin1Num);
        b.Rank(end, out end0Num, out end1Num);
        int range0Num = end0Num - begin0Num;
        int range1Num = end - begin - range0Num;
        if ((x & (1 << bitPos)) != 0) { // choose 0
            if (range0Num > 0) {
                return XorMax(begin0Num, end0Num, x, Left(index), bitPos - 1);
            } else {
                return XorMax(begin1Num, end1Num, x, Right(index), bitPos - 1) | (1 << bitPos);
            }
        } else {
            if (range1Num > 0) {
                return XorMax(begin1Num, end1Num, x, Right(index), bitPos - 1) | (1 << bitPos);
            } else {
                return XorMax(begin0Num, end0Num, x, Left(index), bitPos - 1);
            }
        }
    }
};
// PREWRITEN CODE BEGINS FROM HERE
internal partial class Solver : Scanner {
    public static void Main(string[] args) {
#if LOCAL
        byte[] inputBuffer = new byte[1000000];
        var inputStream = Console.OpenStandardInput(inputBuffer.Length);
        Console.SetIn(new StreamReader(inputStream, Console.InputEncoding, false, inputBuffer.Length));
        new Solver(Console.In, Console.Out).Run();
#else
        Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false });
        new Solver(Console.In, Console.Out).Run();
        Console.Out.Flush();
#endif
    }

#pragma warning disable IDE0052
    private readonly TextReader cin;
    private readonly TextWriter cout;
#pragma warning restore IDE0052

    public Solver(TextReader reader, TextWriter writer)
        : base(reader) {
        cin = reader;
        cout = writer;
    }
    public Solver(string input, TextWriter writer)
        : this(new StringReader(input), writer) {
    }

#pragma warning disable IDE1006
#pragma warning disable IDE0051
    private int ni() { return NextInt(); }
    private int[] ni(int n) { return NextIntArray(n); }
    private long nl() { return NextLong(); }
    private long[] nl(int n) { return NextLongArray(n); }
    private double nd() { return NextDouble(); }
    private double[] nd(int n) { return NextDoubleArray(n); }
    private string ns() { return Next(); }
    private string[] ns(int n) { return NextArray(n); }
#pragma warning restore IDE1006
#pragma warning restore IDE0051
}

internal static class LinqPadExtension {
    public static T Dump<T>(this T obj) {
#if LOCAL
        return LINQPad.Extensions.Dump(obj);
#else
        return obj;
#endif
    }
}

public class Scanner {
    private readonly TextReader Reader;
    private readonly Queue<string> TokenQueue = new Queue<string>();
    private readonly CultureInfo ci = CultureInfo.InvariantCulture;

    public Scanner()
        : this(Console.In) {
    }

    public Scanner(TextReader reader) {
        Reader = reader;
    }

    public int NextInt() { return int.Parse(Next(), ci); }
    public long NextLong() { return long.Parse(Next(), ci); }
    public double NextDouble() { return double.Parse(Next(), ci); }
    public string[] NextArray(int size) {
        string[] array = new string[size];
        for (int i = 0; i < size; i++) {
            array[i] = Next();
        }

        return array;
    }
    public int[] NextIntArray(int size) {
        int[] array = new int[size];
        for (int i = 0; i < size; i++) {
            array[i] = NextInt();
        }

        return array;
    }

    public long[] NextLongArray(int size) {
        long[] array = new long[size];
        for (int i = 0; i < size; i++) {
            array[i] = NextLong();
        }

        return array;
    }

    public double[] NextDoubleArray(int size) {
        double[] array = new double[size];
        for (int i = 0; i < size; i++) {
            array[i] = NextDouble();
        }

        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 static readonly char[] _separator = new[] { ' ', '\t' };
    private bool StockTokens() {
        while (true) {
            string line = Reader.ReadLine();
            if (line == null) {
                return false;
            }

            string[] tokens = line.Split(_separator, StringSplitOptions.RemoveEmptyEntries);
            if (tokens.Length == 0) {
                continue;
            }

            foreach (string token in tokens) {
                TokenQueue.Enqueue(token);
            }

            return true;
        }
    }
}