結果
問題 | No.2421 entersys? |
ユーザー |
|
提出日時 | 2023-08-20 20:24:39 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 2,103 ms / 3,000 ms |
コード長 | 7,281 bytes |
コンパイル時間 | 2,655 ms |
コンパイル使用メモリ | 120,712 KB |
実行使用メモリ | 151,032 KB |
最終ジャッジ日時 | 2024-12-14 02:46:35 |
合計ジャッジ時間 | 33,480 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 28 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
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;}}}