結果

問題 No.2421 entersys?
ユーザー 👑 kakel-sankakel-san
提出日時 2023-08-20 20:24:39
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 2,671 ms / 3,000 ms
コード長 7,281 bytes
コンパイル時間 1,408 ms
コンパイル使用メモリ 110,592 KB
実行使用メモリ 143,880 KB
最終ジャッジ日時 2024-05-08 02:52:07
合計ジャッジ時間 37,384 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 42 ms
20,608 KB
testcase_01 AC 44 ms
20,992 KB
testcase_02 AC 49 ms
21,760 KB
testcase_03 AC 43 ms
20,480 KB
testcase_04 AC 44 ms
20,992 KB
testcase_05 AC 47 ms
21,544 KB
testcase_06 AC 56 ms
21,532 KB
testcase_07 AC 46 ms
21,664 KB
testcase_08 AC 49 ms
21,632 KB
testcase_09 AC 50 ms
22,140 KB
testcase_10 AC 43 ms
21,272 KB
testcase_11 AC 1,878 ms
118,456 KB
testcase_12 AC 1,895 ms
118,564 KB
testcase_13 AC 1,874 ms
118,236 KB
testcase_14 AC 1,835 ms
118,248 KB
testcase_15 AC 1,854 ms
118,236 KB
testcase_16 AC 1,932 ms
127,564 KB
testcase_17 AC 1,909 ms
127,752 KB
testcase_18 AC 1,933 ms
127,264 KB
testcase_19 AC 1,905 ms
127,584 KB
testcase_20 AC 1,917 ms
127,700 KB
testcase_21 AC 1,655 ms
127,528 KB
testcase_22 AC 1,473 ms
107,908 KB
testcase_23 AC 2,443 ms
143,760 KB
testcase_24 AC 2,486 ms
143,880 KB
testcase_25 AC 2,671 ms
143,760 KB
testcase_26 AC 1,135 ms
93,196 KB
testcase_27 AC 1,131 ms
93,192 KB
testcase_28 AC 1,119 ms
93,180 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

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 string[] SList(long n) => Enumerable.Repeat(0, (int)n).Select(_ => ReadLine()).ToArray();
    public static void Main()
    {
        Solve();
    }
    static void Solve()
    {
        var n = NN;
        var _map = SList(n);
        var q = NN;
        var _query = SList(q);
        var map = new (string x, int l, int r)[n];
        for (var i = 0; i < n; ++i)
        {
            var s = _map[i].Split();
            map[i] = (s[0], int.Parse(s[1]), int.Parse(s[2]));
        }
        var query = new (int id, string x, int l, int r)[q];
        for (var i = 0; i < q; ++i)
        {
            var s = _query[i].Split();
            var id = int.Parse(s[0]);
            if (id == 1) query[i] = (id, s[1], int.Parse(s[2]), 0);
            else if (id == 2) query[i] = (id, "", int.Parse(s[1]), 0);
            else query[i] = (id, s[1], int.Parse(s[2]), int.Parse(s[3]));
        }
        var allset = new HashSet<int>();
        var dic = new Dictionary<string, HashSet<int>>();
        for (var i = 0; i < map.Length; ++i)
        {
            allset.Add(map[i].l);
            allset.Add(map[i].r + 1);
            if (!dic.ContainsKey(map[i].x)) dic[map[i].x] = new HashSet<int>();
            dic[map[i].x].Add(map[i].l);
            dic[map[i].x].Add(map[i].r + 1);
        }
        for (var i = 0; i < query.Length; ++i)
        {
            if (query[i].id == 1)
            {
                if (!dic.ContainsKey(query[i].x)) dic[query[i].x] = new HashSet<int>();
                dic[query[i].x].Add(query[i].l);
                allset.Add(query[i].l);
            }
            else if (query[i].id == 2)
            {
                allset.Add(query[i].l);
            }
            else
            {
                if (!dic.ContainsKey(query[i].x)) dic[query[i].x] = new HashSet<int>();
                dic[query[i].x].Add(query[i].l);
                dic[query[i].x].Add(query[i].r + 1);
                allset.Add(query[i].l);
                allset.Add(query[i].r + 1);
            }
        }
        var posmap = new Dictionary<string, List<int>>();
        foreach (var kv in dic)
        {
            posmap[kv.Key] = new List<int>(kv.Value);
            posmap[kv.Key].Sort();
        }
        var segmap = new Dictionary<string, LazyAddSumSegmentTree>();
        foreach (var kv in dic) segmap[kv.Key] = new LazyAddSumSegmentTree(Enumerable.Repeat(0, kv.Value.Count).ToArray());
        var alllist = new List<int>(allset);
        alllist.Sort();
        var allseg = new LazyAddSumSegmentTree(Enumerable.Repeat(0, alllist.Count).ToArray());
        for (var i = 0; i < map.Length; ++i)
        {
            var lpos = LowerBound(0, map[i].l, posmap[map[i].x]);
            var rpos = LowerBound(0, map[i].r + 1, posmap[map[i].x]);
            segmap[map[i].x].AddRange(lpos, rpos, 1);
            lpos = LowerBound(0, map[i].l, alllist);
            rpos = LowerBound(0, map[i].r + 1, alllist);
            allseg.AddRange(lpos, rpos, 1);
        }
        var ans = new List<string>();
        for (var i = 0; i < query.Length; ++i)
        {
            if (query[i].id == 1)
            {
                var pos = LowerBound(0, query[i].l, posmap[query[i].x]);
                ans.Add(segmap[query[i].x].Get(pos, pos + 1) == 1 ? "Yes" : "No");
            }
            else if (query[i].id == 2)
            {
                var pos = LowerBound(0, query[i].l, alllist);
                ans.Add(allseg.Get(pos, pos + 1).ToString());
            }
            else
            {
                var lpos = LowerBound(0, query[i].l, posmap[query[i].x]);
                var rpos = LowerBound(0, query[i].r + 1, posmap[query[i].x]);
                segmap[query[i].x].AddRange(lpos, rpos, 1);
                lpos = LowerBound(0, query[i].l, alllist);
                rpos = LowerBound(0, query[i].r + 1, alllist);
                allseg.AddRange(lpos, rpos, 1);
            }
        }
        WriteLine(string.Join("\n", ans));
    }
    static int LowerBound(int left, int min, List<int> list)
    {
        if (list[left] >= min) return left;
        var ng = left;
        var ok = list.Count;
        while (ok - ng > 1)
        {
            var center = (ng + ok) / 2;
            if (list[center] < min) ng = center;
            else ok = center;
        }
        return ok;
    }
    class LazyAddSumSegmentTree
    {
        public long[] tree;
        public long[] lazy;
        /// <summary>範囲外を参照したときの値 欲しい値の種類によって変える</summary>
        long INF = 0;
        int size;
        public LazyAddSumSegmentTree(int[] list)
        {
            size = 1;
            while (size < list.Length) size <<= 1;
            tree = Enumerable.Repeat(INF, size * 2).ToArray();
            lazy = Enumerable.Repeat(INF, size * 2).ToArray();
            for (var i = 0; i < list.Length; ++i) tree[i + size] = list[i];
            for (var i = size - 1; i >= 1; --i) tree[i] = Calc(tree[i * 2], tree[i * 2 + 1]);
        }
        /// <summary>取得時の評価 欲しい値の種類によって変える</summary>
        long Calc(long a, long b)
        {
            return a + b;
        }
        /// <summary>遅延評価の値を適用する 区間に対する操作によって変える</summary>
        long Leval(long tval, long lval)
        {
            return tval + lval;
        }
        void Eval(int k)
        {
            if (lazy[k] == INF) return;
            if (k < size)
            {
                lazy[k * 2] = Calc(lazy[k * 2], lazy[k] / 2);
                lazy[k * 2 + 1] = Calc(lazy[k * 2 + 1], lazy[k] / 2);
            }
            tree[k] = Leval(tree[k], lazy[k]);
            lazy[k] = INF;
        }
        /// <summary>区間加算(end is not include)</summary>
        public void AddRange(int begin, int end, long value, int k = 1, int l = 0, int r = -1)
        {
            if (r < 0) r = size;
            Eval(k);
            if (begin <= l && r <= end)
            {
                lazy[k] += (r - l) * value;
                Eval(k);
            }
            else if (begin < r && l < end)
            {
                AddRange(begin, end, value, k * 2, l, (l + r) / 2);
                AddRange(begin, end, value, k * 2 + 1, (l + r) / 2, r);
                tree[k] = Calc(tree[k * 2], tree[k * 2 + 1]);
            }
        }
        /// <summary>値の取得(end is not include)</summary>
        public long Get(int begin, int end, int k = 1, int l = 0, int r = -1)
        {
            if (r < 0) r = size;
            Eval(k);
            if (begin <= l && r <= end) return tree[k];
            else if (begin < r && l < end)
                return Calc(Get(begin, end, k * 2, l, (l + r) / 2), Get(begin, end, k * 2 + 1, (l + r) / 2, r));
            else return INF;
        }
    }
}
0