#134751 (C#(csc)) No.449 ゆきこーだーの雨と雪 (4)

提出ソース

結果

問題	No.449 ゆきこーだーの雨と雪 (4)
ユーザー	eitaho
提出日時	2016-12-03 15:48:14
言語	C#(csc) (csc 3.9.0)
結果	AC
実行時間	383 ms / 5,000 ms
コード長	11,114 bytes
コンパイル時間	1,434 ms
コンパイル使用メモリ	117,892 KB
実行使用メモリ	54,272 KB
最終ジャッジ日時	2023-10-23 16:05:04
合計ジャッジ時間	14,641 ms
ジャッジサーバーID （参考情報）	judge14 / judge13

このコードへのチャレンジ（β）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	37 ms 24,628 KB
testcase_01	AC	36 ms 24,696 KB
testcase_02	AC	37 ms 24,556 KB
testcase_03	AC	39 ms 24,688 KB
testcase_04	AC	41 ms 24,688 KB
testcase_05	AC	38 ms 24,688 KB
testcase_06	AC	42 ms 24,688 KB
testcase_07	AC	42 ms 24,688 KB
testcase_08	AC	39 ms 24,688 KB
testcase_09	AC	39 ms 24,688 KB
testcase_10	AC	35 ms 24,688 KB
testcase_11	AC	40 ms 24,688 KB
testcase_12	AC	274 ms 45,096 KB
testcase_13	AC	344 ms 47,948 KB
testcase_14	AC	319 ms 47,924 KB
testcase_15	AC	383 ms 47,892 KB
testcase_16	AC	332 ms 47,816 KB
testcase_17	AC	363 ms 47,872 KB
testcase_18	AC	287 ms 45,072 KB
testcase_19	AC	317 ms 47,872 KB
testcase_20	AC	304 ms 47,812 KB
testcase_21	AC	340 ms 47,832 KB
testcase_22	AC	321 ms 47,936 KB
testcase_23	AC	294 ms 45,260 KB
testcase_24	AC	322 ms 47,872 KB
testcase_25	AC	259 ms 45,072 KB
testcase_26	AC	260 ms 43,124 KB
testcase_27	AC	358 ms 47,816 KB
testcase_28	AC	331 ms 47,892 KB
testcase_29	AC	300 ms 47,812 KB
testcase_30	AC	348 ms 47,916 KB
testcase_31	AC	324 ms 47,948 KB
testcase_32	AC	286 ms 47,924 KB
testcase_33	AC	319 ms 47,968 KB
testcase_34	AC	262 ms 45,468 KB
testcase_35	AC	344 ms 47,968 KB
testcase_36	AC	266 ms 45,316 KB
testcase_37	AC	255 ms 54,272 KB
testcase_38	AC	241 ms 47,924 KB
testcase_39	AC	219 ms 47,924 KB
testcase_40	AC	208 ms 47,924 KB
testcase_41	AC	267 ms 50,416 KB
testcase_42	AC	260 ms 50,416 KB
testcase_43	AC	231 ms 44,636 KB
testcase_44	AC	249 ms 47,240 KB
testcase_45	AC	236 ms 54,272 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

raw source code

using System;
using System.IO;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.Collections.Generic;
using System.Diagnostics;
using System.Numerics;
using Enu = System.Linq.Enumerable;

public class Program
{
    public void Solve()
    {
        int NP = Reader.Int();
        var P = Reader.IntArray(NP);
        int Q = Reader.Int();
        var table = Reader.StringTable(Q);
        var name = new Dictionary<string, int>();
        var solved = new int[NP];
        var score = new long[Q];
        var scoreCount = new Dictionary<int, int>();
        var tree = new AVLTreeSortedSet();

        Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false });
        foreach (var t in table)
        {
            int who = name[t[0]] = name.ContainsKey(t[0]) ? name[t[0]] : name.Count;
            int prob = t[1][0] - 'A';
            if (t[1] == "?")
                Console.WriteLine(tree.Count - tree.LowerBound(score[who]));
            else
            {
                if (score[who] > 0) tree.Remove(score[who]);
                int s = (int)(score[who] >> 32) + 50 * P[prob] + 500 * P[prob] / (8 + 2 * ++solved[prob]);
                scoreCount[s] = scoreCount.ContainsKey(s) ? scoreCount[s] + 1 : 1;
                score[who] = ((long)s << 32) + (Q - scoreCount[s]);
                tree.Add(score[who]);
            }
        }
        Console.Out.Flush();
    }
}


public class AVLTreeSortedSet
{
    public struct Node
    {
        public int L, R, Count;
        public byte MaxDepth;
        public long Val;
    }
    const int PoolSize = (int)2e5;
    const int None = 0, NotFound = -1;
    Node[] nodes = new Node[PoolSize + 1];
    int nodeIndex = 1;

    public int Count { get { return nodes[Root].Count; } }
    public int MaxDepth { get { return nodes[Root].MaxDepth; } }
    int Root = None;

    int GenNode(long val)
    {
        nodes[nodeIndex].Val = val;
        nodes[nodeIndex].MaxDepth = 1;
        nodes[nodeIndex].Count = 1;
        nodes[nodeIndex].L = nodes[nodeIndex].R = None;
        return nodeIndex++;
    }

    void Update(int i)
    {
        Debug.Assert(i > None);
        nodes[i].Count = 1 + nodes[nodes[i].L].Count + nodes[nodes[i].R].Count;
        nodes[i].MaxDepth = (byte)(1 + Math.Max(nodes[nodes[i].L].MaxDepth, nodes[nodes[i].R].MaxDepth));
    }

    public void Clear() { Root = None; nodeIndex = 1; }

    public bool Add(long val)
    {
        int node = Add(Root, GenNode(val), val);
        if (node == None) return false;
        Root = node;
        return true;
    }
    int Add(int i, int newNodeIndex, long val)
    {
        if (i == None) return newNodeIndex;
        if (val == nodes[i].Val) return None;
        if (val < nodes[i].Val)
        {
            int child = Add(nodes[i].L, newNodeIndex, val);
            if (child == None) return None;
            nodes[i].L = child; Update(i);
        }
        else
        {
            int child = Add(nodes[i].R, newNodeIndex, val);
            if (child == None) return None;
            nodes[i].R = child; Update(i);
        }
        return Rebalance(i);
    }

    public long this[int index]
    {
        get
        {
            if (index < 0 || index >= Count) throw new ArgumentException();
            int i = Root, Lsize;
            while (index != (Lsize = nodes[nodes[i].L].Count))
                if (index < Lsize) i = nodes[i].L;
                else { index -= Lsize + 1; i = nodes[i].R; }
            return nodes[i].Val;
        }
    }

    public bool Contains(long val)
    {
        for (int i = Root; i != None; )
            if (val == nodes[i].Val) return true;
            else if (val < nodes[i].Val) i = nodes[i].L;
            else i = nodes[i].R;
        return false;
    }
    public int IndexOf(long val)
    {
        for (int i = Root, index = 0; i != None; )
            if (val == nodes[i].Val) return index + nodes[nodes[i].L].Count;
            else if (val < nodes[i].Val) i = nodes[i].L;
            else { index += 1 + nodes[nodes[i].L].Count; i = nodes[i].R; }
        return -1;
    }


    // Count node.Val < val
    public int LowerBound(long val) { long d; return LowerBound(val, out d); }
    public int LowerBound(long val, out long resVal)
    {
        int index = 0;
        resVal = long.MaxValue;
        for (int i = Root; i != None; )
            if (nodes[i].Val >= val) { resVal = nodes[i].Val; i = nodes[i].L; }
            else { index += 1 + nodes[nodes[i].L].Count; i = nodes[i].R; }
        return index;
    }

    // Count node.Val <= val
    public int UpperBound(long val) { long d; return UpperBound(val, out d); }
    public int UpperBound(long val, out long resVal)
    {
        int index = 0;
        resVal = long.MaxValue;
        for (int i = Root; i != None; )
            if (nodes[i].Val > val) { resVal = nodes[i].Val; i = nodes[i].L; }
            else { index += 1 + nodes[nodes[i].L].Count; i = nodes[i].R; }
        return index;
    }

    public bool Remove(long val)
    {
        int node = Remove(Root, val);
        if (node == NotFound) return false;
        Root = node;
        return true;
    }
    int Remove(int i, long val)
    {
        if (i == None) return NotFound;
        if (val == nodes[i].Val) return RemoveNode(i);
        if (val < nodes[i].Val)
        {
            int child = Remove(nodes[i].L, val);
            if (child == NotFound) return NotFound;
            nodes[i].L = child; Update(i);
        }
        else
        {
            int child = Remove(nodes[i].R, val);
            if (child == NotFound) return NotFound;
            nodes[i].R = child; Update(i);
        }
        return Rebalance(i);
    }

    public void RemoveAt(int index)
    {
        if (index < 0 || index >= Count) throw new ArgumentException();
        Root = RemoveAt(index, Root);
    }
    int RemoveAt(int index, int i)
    {
        int Lsize = nodes[nodes[i].L].Count;
        if (index == Lsize) return RemoveNode(i);
        if (index < Lsize)
            nodes[i].L = RemoveAt(index, nodes[i].L);
        else
            nodes[i].R = RemoveAt(index - Lsize - 1, nodes[i].R);
        Update(i);
        return Rebalance(i);
    }
    int RemoveNode(int i)
    {
        int L = nodes[i].L, R = nodes[i].R;
        if (L == None && R == None) return None;
        if (L == None) return R;
        if (R == None) return L;
        int minNode = 0;
        R = MoveMin(R, ref minNode);
        nodes[minNode].L = L;
        nodes[minNode].R = R;
        Update(minNode);
        return Rebalance(minNode);
    }
    int MoveMin(int i, ref int minNode)
    {
        if (nodes[i].L == None) { minNode = i; return nodes[i].R; }
        nodes[i].L = MoveMin(nodes[i].L, ref minNode);
        Update(i);
        return Rebalance(i);
    }


    public long[] ToArray()
    {
        long[] res = new long[Count];
        if (Count == 0) return res;
        ToArrayRec(Root, 0, res);
        return res;
    }
    void ToArrayRec(int i, int resL, long[] res)
    {
        int Lsize = nodes[nodes[i].L].Count;
        if (Lsize > 0) ToArrayRec(nodes[i].L, resL, res);
        res[resL + Lsize] = nodes[i].Val;
        if (nodes[i].R != None) ToArrayRec(nodes[i].R, resL + Lsize + 1, res);
    }


    int Rebalance(int i)
    {
        int L = nodes[i].L, R = nodes[i].R;
        switch (nodes[L].MaxDepth - nodes[R].MaxDepth)
        {
            case 2:
                if (nodes[nodes[L].L].MaxDepth < nodes[nodes[L].R].MaxDepth)
                    RotateLR(i);
                return RotateLL(i);
            case -2:
                if (nodes[nodes[R].R].MaxDepth < nodes[nodes[R].L].MaxDepth)
                    RotateRL(i);
                return RotateRR(i);
            default:
                return i;
        }
    }
    void RotateLR(int i)
    {
        int A = nodes[i].L, B = nodes[A].R;
        nodes[A].R = nodes[B].L; Update(A);
        nodes[B].L = A; Update(B);
        nodes[i].L = B; Update(i);
    }
    int RotateLL(int i)
    {
        int B = nodes[i].L;
        nodes[i].L = nodes[B].R; Update(i);
        nodes[B].R = i; Update(B);
        return B;
    }
    void RotateRL(int i)
    {
        int A = nodes[i].R, B = nodes[A].L;
        nodes[A].L = nodes[B].R; Update(A);
        nodes[B].R = A; Update(B);
        nodes[i].R = B; Update(i);
    }
    int RotateRR(int i)
    {
        int B = nodes[i].R;
        nodes[i].R = nodes[B].L; Update(i);
        nodes[B].L = i; Update(B);
        return B;
    }

    public bool Exam(int i = -1)
    {
        if (i == -1) i = Root;
        if (i == None) return true;
        int L = nodes[i].L, R = nodes[i].R;
        if (nodes[i].MaxDepth != 1 + Math.Max(nodes[L].MaxDepth, nodes[R].MaxDepth))
            return false;
        if (Math.Abs(nodes[L].MaxDepth - nodes[R].MaxDepth) > 1)
            return false;
        return Exam(L) && Exam(R);
    }
    public void ShowEdges(int i = -1)
    {
        if (i == -1) i = Root;
        if (i == None) return;
        if (nodes[i].L != None)
            Console.WriteLine(nodes[i].Val + " " + nodes[nodes[i].L].Val);
        if (nodes[i].R != None)
            Console.WriteLine(nodes[i].Val + " " + nodes[nodes[i].R].Val);
        ShowEdges(nodes[i].L);
        ShowEdges(nodes[i].R);
    }
}



class Entry { static void Main() { new Program().Solve(); } }
class Reader
{
    static TextReader reader = Console.In;
    static readonly char[] separator = { ' ' };
    static readonly StringSplitOptions op = StringSplitOptions.RemoveEmptyEntries;
    static string[] A = new string[0];
    static int i;
    static void Init() { A = new string[0]; }
    public static void Set(TextReader r) { reader = r; Init(); }
    public static void Set(string file) { reader = new StreamReader(file); Init(); }
    public static bool HasNext() { return CheckNext(); }
    public static string String() { return Next(); }
    public static int Int() { return int.Parse(Next()); }
    public static long Long() { return long.Parse(Next()); }
    public static double Double() { return double.Parse(Next()); }
    public static int[] IntLine() { return Array.ConvertAll(Split(Line()), int.Parse); }
    public static int[] IntArray(int N) { return Range(N, Int); }
    public static int[][] IntTable(int H) { return Range(H, IntLine); }
    public static string[] StringArray(int N) { return Range(N, Next); }
    public static string[][] StringTable(int N) { return Range(N, () => Split(Line())); }
    public static string Line() { return reader.ReadLine().Trim(); }
    public static T[] Range<T>(int N, Func<T> f) { var r = new T[N]; for (int i = 0; i < N; r[i++] = f()) ; return r; }
    static string[] Split(string s) { return s.Split(separator, op); }
    static string Next() { CheckNext(); return A[i++]; }
    static bool CheckNext()
    {
        if (i < A.Length) return true;
        string line = reader.ReadLine();
        if (line == null) return false;
        if (line == "") return CheckNext();
        A = Split(line);
        i = 0;
        return true;
    }
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード