結果
| 問題 | No.1675 Strange Minimum Query |
| ユーザー |
👑  kakel-san
|
| 提出日時 | 2024-01-03 23:05:46 |
| 言語 | C# (.NET 8.0.203) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 11,330 bytes |
| コンパイル時間 | 14,888 ms |
| コンパイル使用メモリ | 158,896 KB |
| 実行使用メモリ | 218,248 KB |
| 最終ジャッジ日時 | 2024-01-03 23:06:21 |
| 合計ジャッジ時間 | 34,296 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge12 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 83 ms
32,932 KB |
| testcase_01 | AC | 82 ms
32,804 KB |
| testcase_02 | AC | 84 ms
32,932 KB |
| testcase_03 | AC | 608 ms
64,388 KB |
| testcase_04 | AC | 680 ms
65,920 KB |
| testcase_05 | AC | 131 ms
38,052 KB |
| testcase_06 | AC | 688 ms
64,620 KB |
| testcase_07 | AC | 724 ms
66,408 KB |
| testcase_08 | AC | 84 ms
33,188 KB |
| testcase_09 | AC | 87 ms
33,572 KB |
| testcase_10 | AC | 263 ms
71,664 KB |
| testcase_11 | AC | 118 ms
43,172 KB |
| testcase_12 | AC | 255 ms
72,184 KB |
| testcase_13 | AC | 420 ms
80,312 KB |
| testcase_14 | AC | 630 ms
73,396 KB |
| testcase_15 | AC | 645 ms
73,844 KB |
| testcase_16 | AC | 84 ms
32,932 KB |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | WA | - |
| testcase_20 | WA | - |
| testcase_21 | WA | - |
| testcase_22 | WA | - |
| testcase_23 | WA | - |
| testcase_24 | WA | - |
| testcase_25 | WA | - |
| testcase_26 | WA | - |
| testcase_27 | WA | - |
| testcase_28 | WA | - |
| testcase_29 | WA | - |
| testcase_30 | WA | - |
| testcase_31 | WA | - |
| testcase_32 | WA | - |
| testcase_33 | WA | - |
| testcase_34 | WA | - |
| testcase_35 | WA | - |
| testcase_36 | WA | - |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (100 ms)。 MSBuild のバージョン 17.7.3+8ec440e68 (.NET) main -> /home/judge/data/code/bin/Release/net7.0/main.dll main -> /home/judge/data/code/bin/Release/net7.0/publish/
ソースコード
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);
Array.Sort(map, (l, r) =>
{
var d = l[0].CompareTo(r[0]);
if (d != 0) return d;
return r[2].CompareTo(l[2]);
});
var set = new AvlTree<int>();
var ans = new int[n];
var apos = 0;
var dpos = 0;
for (var i = 0; i < n; ++i)
{
while (dpos < map.Length && map[dpos][1] - 1 < i)
{
set.Delete(map[dpos][2]);
++dpos;
}
while (apos < map.Length && map[apos][0] - 1 == i)
{
set.Insert(map[apos][2]);
++apos;
}
if (set.GetCount() == 0) ans[i] = 1;
else ans[i] = set.ElementAt(set.GetCount() - 1);
}
var seg = new SegmentTree<int>(ans, new SegOp());
foreach (var que in map)
{
if (seg.Prod(que[0] - 1, que[1]) != que[2])
{
WriteLine(-1);
return;
}
}
WriteLine(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);
}
}
}