結果

問題 No.2421 entersys?
ユーザー kakel-san
提出日時 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.

ソースコード

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;
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0