Submission #1416929

---

Source Code Expand

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Text;
using System.Globalization;
using System.Diagnostics;



class Myon
{
    public Myon() { }
    public static int Main()
    {
        new Myon().calc();
        return 0;
    }

    Scanner cin;

    long[] ar;
    void calc()
    {
        cin = new Scanner();
        int N = cin.nextInt();
        int M = cin.nextInt();
        int H = cin.nextInt();
        ar = new long[N + M + 10];
        int cnt = 1;
        BIT bit = new BIT(N + M + 10);
        for (int i = 0; i < N; i++)
        {
            ar[cnt] = cin.nextLong();
            bit.bitUpdate(cnt, ar[cnt]);
            cnt++;
        }

        for (int i = 0; i < M; i++)
        {
            string op = cin.next();
            long arg = cin.nextLong();
            if(op == "add")
            {
                ar[cnt] = arg;
                bit.bitUpdate(cnt, arg);
                cnt++;
            }
            else
            {
                long low = arg - H;
                long high = arg + H;
                int ok = cnt + 3;
                int ng = 0;
                while(ok - ng > 1)
                {
                    int mid = (ok + ng) / 2;
                    if (bit.bitCal(mid) <= low) ng = mid;
                    else ok = mid;
                }
                //Console.WriteLine("sum : " + bit.bitCal(cnt + 13));

                if(ok == cnt + 3)
                {
                    Console.WriteLine("miss");
                    continue;
                }
                long sum = bit.bitCal(ng + 1);
                long all = bit.bitCal(cnt + 3);
                if (sum != all && sum < high) Console.WriteLine("stop");
                else
                {
                    Console.WriteLine("go");
                    bit.bitUpdate(ng + 1, -ar[ng + 1]);
                }

            }
        }
    }

    class BIT
    {
        int bitA;
        long[] bit;
        const int INF = int.MaxValue - 10;

        public BIT(int maxa)
        {
            bitA = maxa;
            bit = new long[bitA + 1];
            for (int i = 0; i < bitA; i++)
            {
                bit[i] = 0;
            }
        }

        public void bitUpdate(int a, long val)
        {
            for (int i = a; i <= bitA; i += i & -i)
            {
                bit[i] += val;
            }
        }

        public long bitCal(int max, int min)
        {
            return bitCal(max) - bitCal(min - 1);
        }

        public long bitCal(int a)
        {
            long ret = 0;
            for (int i = a; i > 0; i &= i - 1)
            {
                ret += bit[i];
            }
            return ret;
        }
    }




}


class Scanner
{
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner()
    {
        s = new string[0];
        i = 0;
    }

    public string next()
    {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();

        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        i = 0;
        return s[i++];
    }

    public int nextInt()
    {
        return int.Parse(next());
    }

    public long nextLong()
    {
        return long.Parse(next());
    }

    public double nextDouble()
    {
        return double.Parse(next());
    }

}

Submission Info

Judge Result