結果

問題 No.449 ゆきこーだーの雨と雪 (4)
ユーザー eitaho
提出日時 2016-12-03 15:48:14
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 278 ms / 5,000 ms
コード長 11,114 bytes
コンパイル時間 1,261 ms
コンパイル使用メモリ 120,656 KB
実行使用メモリ 54,952 KB
最終ジャッジ日時 2024-09-22 10:31:56
合計ジャッジ時間 11,765 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 43
権限があれば一括ダウンロードができます
コンパイルメッセージ
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.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;
    }
}
0