結果

問題 No.1675 Strange Minimum Query
ユーザー kakel-sankakel-san
提出日時 2024-01-03 23:20:42
言語 C#
(.NET 8.0.203)
結果
AC  
実行時間 832 ms / 2,000 ms
コード長 11,364 bytes
コンパイル時間 9,140 ms
コンパイル使用メモリ 168,252 KB
実行使用メモリ 244,452 KB
最終ジャッジ日時 2024-09-27 18:30:59
合計ジャッジ時間 27,311 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 63 ms
31,104 KB
testcase_01 AC 61 ms
30,304 KB
testcase_02 AC 63 ms
31,072 KB
testcase_03 AC 609 ms
62,768 KB
testcase_04 AC 581 ms
65,224 KB
testcase_05 AC 125 ms
46,208 KB
testcase_06 AC 772 ms
63,784 KB
testcase_07 AC 832 ms
64,944 KB
testcase_08 AC 65 ms
31,360 KB
testcase_09 AC 66 ms
31,600 KB
testcase_10 AC 246 ms
76,332 KB
testcase_11 AC 114 ms
50,688 KB
testcase_12 AC 268 ms
77,636 KB
testcase_13 AC 456 ms
88,472 KB
testcase_14 AC 782 ms
90,312 KB
testcase_15 AC 742 ms
90,920 KB
testcase_16 AC 63 ms
31,072 KB
testcase_17 AC 156 ms
49,776 KB
testcase_18 AC 199 ms
56,704 KB
testcase_19 AC 250 ms
77,792 KB
testcase_20 AC 460 ms
77,628 KB
testcase_21 AC 432 ms
77,180 KB
testcase_22 AC 545 ms
79,984 KB
testcase_23 AC 429 ms
69,864 KB
testcase_24 AC 396 ms
70,264 KB
testcase_25 AC 296 ms
66,548 KB
testcase_26 AC 187 ms
57,456 KB
testcase_27 AC 378 ms
77,456 KB
testcase_28 AC 253 ms
74,080 KB
testcase_29 AC 178 ms
64,600 KB
testcase_30 AC 182 ms
56,576 KB
testcase_31 AC 513 ms
70,168 KB
testcase_32 AC 684 ms
80,404 KB
testcase_33 AC 695 ms
80,408 KB
testcase_34 AC 684 ms
80,540 KB
testcase_35 AC 617 ms
85,272 KB
testcase_36 AC 631 ms
244,452 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (101 ms)。
MSBuild のバージョン 17.9.6+a4ecab324 (.NET)
  main -> /home/judge/data/code/bin/Release/net8.0/main.dll
  main -> /home/judge/data/code/bin/Release/net8.0/publish/

ソースコード

diff # 

using System;
using static System.Console;
using System.Linq;
using System.Collections.Generic;

class Program
{
    static int NN => int.Parse(ReadLine());
    static int[] NList => ReadLine().Split().Select(int.Parse).ToArray();
    static int[][] NArr(long n) => Enumerable.Repeat(0, (int)n).Select(_ => NList).ToArray();
    public static void Main()
    {
        Solve();
    }
    static void Solve()
    {
        var c = NList;
        var (n, q) = (c[0], c[1]);
        var map = NArr(q);
        WriteLine(Query(n, q, map));
    }
    static string Query(int n, int q, int[][] map)
    {
        var addlist = new List<int>[n];
        var dellist = new List<int>[n];
        for (var i = 0; i < n; ++i)
        {
            addlist[i] = new List<int>();
            dellist[i] = new List<int>();
        }
        foreach (var query in map)
        {
            addlist[query[0] - 1].Add(query[2]);
            dellist[query[1] - 1].Add(query[2]);
        }
        var set = new AvlTree<int>();
        var ans = new int[n];
        for (var i = 0; i < n; ++i)
        {
            foreach (var add in addlist[i]) set.Insert(add);
            if (set.GetCount() == 0) ans[i] = 1;
            else ans[i] = set.ElementAt(set.GetCount() - 1);
            foreach (var del in dellist[i]) set.Delete(del);
        }
        var seg = new SegmentTree<int>(ans, new SegOp());
        foreach (var que in map)
        {
            if (seg.Prod(que[0] - 1, que[1]) != que[2])
            {
                return "-1";
            }
        }
        return string.Join(" ", ans);
    }
    public class AvlTree<T> where T: IComparable<T>
    {
        private class Node<U> where U: IComparable<U>
        {
            public U Value;
            public Node<U> Lc = null;
            public Node<U> Rc = null;
            public int Height;
            public int Count;
            public int CCount;
            public Node(int height, U value)
            {
                Height = height;
                Count = 1;
                CCount = 1;
                Value = value;
            }
        }
        private Node<T> root = null;
        static int GetHeight(Node<T> t)
        {
            return t == null ? 0 : t.Height;
        }
        static int GetCount(Node<T> t)
        {
            return t == null ? 0 : t.Count;
        }
        static int GetBalance(Node<T> t)
        {
            return GetHeight(t.Lc) - GetHeight(t.Rc);
        }
        static void Recalc(Node<T> t)
        {
            if (t == null) return;
            t.Height = 1 + Math.Max(GetHeight(t.Lc), GetHeight(t.Rc));
            t.Count = t.CCount + GetCount(t.Lc) + GetCount(t.Rc);
        }
        static Node<T> RotateLeft(Node<T> t)
        {
            Node<T> u = t.Rc;
            Node<T> t2 = u.Lc;
            u.Lc = t;
            t.Rc = t2;
            Recalc(t);
            Recalc(u);
            return u;
        }
        static Node<T> RotateRight(Node<T> t)
        {
            Node<T> u = t.Lc;
            Node<T> t2 = u.Rc;
            u.Rc = t;
            t.Lc = t2;
            Recalc(t);
            Recalc(u);
            return u;
        }
        static Node<T> RotateLR(Node<T> t)
        {
            t.Lc = RotateLeft(t.Lc);
            return RotateRight(t);
        }
        static Node<T> RotateRL(Node<T> t)
        {
            t.Rc = RotateRight(t.Rc);
            return RotateLeft(t);
        }
        static Node<T> BalanceLeft(Node<T> t)
        {
            if (GetBalance(t) > 1)
            {
                if (GetBalance(t.Lc) < 0) t = RotateLR(t);
                else t = RotateRight(t);
            }
            Recalc(t);
            return t;
        }
        static Node<T> BalanceRight(Node<T> t)
        {
            if (GetBalance(t) < -1)
            {
                if (GetBalance(t.Rc) > 0) t = RotateRL(t);
                else t = RotateLeft(t);
            }
            Recalc(t);
            return t;
        }
        /// <summary>valueを挿入する</summary>
        public void Insert(T value)
        {
            root = Insert(root, value);
        }
        Node<T> Insert(Node<T> cur, T value)
        {
            if (cur == null)
            {
                return new Node<T>(1, value);
            }
            var d = value.CompareTo(cur.Value);
            if (d < 0)
            {
                cur.Lc = Insert(cur.Lc, value);
                return BalanceLeft(cur);
            }
            else if (d > 0)
            {
                cur.Rc = Insert(cur.Rc, value);
                return BalanceRight(cur);
            }
            else
            {
                ++cur.CCount;
                Recalc(cur);
                return cur;
            }
        }
        /// <summary>valueを削除する 存在しない場合はなにもしない</summary>
        public void Delete(T value)
        {
            root = Delete(root, value);
        }
        Node<T> Delete(Node<T> cur, T value)
        {
            if (cur == null) return null;
            var d = value.CompareTo(cur.Value);
            if (d < 0)
            {
                cur.Lc = Delete(cur.Lc, value);
                return BalanceRight(cur);
            }
            else if (d > 0)
            {
                cur.Rc = Delete(cur.Rc, value);
                return BalanceLeft(cur);
            }
            else
            {
                --cur.CCount;
                if (cur.CCount == 0)
                {
                    if (cur.Lc != null)
                    {
                        Node<T> del = null;
                        var max = DeleteMax(cur.Lc, ref del);
                        cur.Lc = max;
                        cur.Value = del.Value;
                        cur.CCount = del.CCount;
                        return BalanceRight(cur);
                    }
                    else
                    {
                        return cur.Rc;
                    }
                }
                else
                {
                    Recalc(cur);
                    return cur;
                }
            }
        }
        Node<T> DeleteMax(Node<T> t, ref Node<T> del)
        {
            if (t.Rc == null)
            {
                del = t;
                return t.Lc;
            }
            else
            {
                var max = DeleteMax(t.Rc, ref del);
                t.Rc = max;
                return BalanceLeft(t);
            }
        }
        /// <summary>小さいほうからpos番目の要素を取得する</summary>
        public T ElementAt(int pos)
        {
            if (pos < 0 || pos >= GetCount(root)) return default;
            var t = ElementAt(root, pos);
            return t.Value;
        }
        /// <summary>小さいほうからpos番目の要素を取得する</summary>
        public T ElementAt(int pos, T defaultValue)
        {
            if (pos < 0 || pos >= GetCount(root)) return defaultValue;
            return ElementAt(pos);
        }
        Node<T> ElementAt(Node<T> cur, int pos)
        {
            if (pos < GetCount(cur.Lc)) return ElementAt(cur.Lc, pos);
            if (pos < GetCount(cur.Lc) + cur.CCount) return cur;
            if (pos < cur.Count) return ElementAt(cur.Rc, pos - GetCount(cur.Lc) - cur.CCount);
            return null;
        }
        public void Debug()
        {
            if (root == null) return;
            Console.WriteLine($"root val:{root.Value}, CCount:{root.CCount}, Count:{root.Count}");
            Debug(root.Value, root.Lc);
            Debug(root.Value, root.Rc);
        }
        void Debug(T pval, Node<T> cur)
        {
            if (cur == null) return;
            Console.WriteLine($"{pval} -> val:{cur.Value}, CCount:{cur.CCount}, Count:{cur.Count}");
            Debug(cur.Value, cur.Lc);
            Debug(cur.Value, cur.Rc);
        }
        /// <summary>value以上でもっとも小さい値とその場所を返却する</summary>
        public T LowerBound(T value, ref int index)
        {
            var cur = root;
            T ans = default;
            var add = 0;
            index = GetCount(root);
            while (cur != null)
            {
                if (value.CompareTo(cur.Value) <= 0)
                {
                    ans = cur.Value;
                    index = add + GetCount(cur.Lc);
                    cur = cur.Lc;
                }
                else
                {
                    add += GetCount(cur.Lc) + cur.CCount;
                    cur = cur.Rc;
                }
            }
            return ans;
        }
        /// <summary>要素の個数を求める</summary>
        public int GetCount()
        {
            return GetCount(root);
        }
    }
    struct SegOp : ISegmentTreeOperator<int>
    {
        public int Identity => int.MaxValue;
        public int Operate(int x, int y)
        {
            return Math.Min(x, y);
        }
    }
    interface ISegmentTreeOperator<T>
    {
        T Identity { get; }
        T Operate(T x, T y);
    }
    class SegmentTree<T>
    {
        int size;
        int log;
        T[] d;
        ISegmentTreeOperator<T> op;
        void Update(int k)
        {
            d[k] = op.Operate(d[2 * k], d[2 * k + 1]);
        }
        public SegmentTree(int n, ISegmentTreeOperator<T> op)
        {
            this.op = op;
            size = 1;
            while (size < n) size <<= 1;
            log = CountRZero(size);
            d = new T[2 * size];
            for (var i = 0; i < d.Length; ++i) d[i] = op.Identity;
        }
        public SegmentTree(T[] v, ISegmentTreeOperator<T> op)
        {
            this.op = op;
            size = 1;
            while (size < v.Length) size <<= 1;
            log = CountRZero(size);
            d = new T[2 * size];
            for (var i = 0; i < size; ++i) d[i] = op.Identity;
            for (var i = 0; i < v.Length; ++i) d[size + i] = v[i];
            for (var i = size - 1; i >= 1; --i) Update(i);
        }
        int CountRZero(int n)
        {
            var ans = 0;
            while (n % 2 == 0)
            {
                ++ans;
                n >>= 1;
            }
            return ans;
        }
        public T this[int p]
        {
            get { return d[p + size]; }
            set
            {
                p += size;
                d[p] = value;
                for (var i = 1; i <= log; ++i) Update(p >> i);
            }
        }
        public T Prod(int l, int r)
        {
            var sml = op.Identity;
            var smr = op.Identity;
            l += size;
            r += size;
            while (l < r)
            {
                if ((l & 1) != 0) sml = op.Operate(sml, d[l++]);
                if ((r & 1) != 0) smr = op.Operate(d[--r], smr);
                l >>= 1;
                r >>= 1;
            }
            return op.Operate(sml, smr);
        }
    }
}
0