結果
| 問題 |
No.1439 Let's Compare!!!!
|
| コンテスト | |
| ユーザー |
 bluemegane
|
| 提出日時 | 2021-03-27 10:58:30 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 8,302 bytes |
| コンパイル時間 | 1,765 ms |
| コンパイル使用メモリ | 116,488 KB |
| 実行使用メモリ | 35,328 KB |
| 最終ジャッジ日時 | 2024-11-29 08:11:41 |
| 合計ジャッジ時間 | 7,707 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 15 RE * 2 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System.Collections.Generic;
using static System.Math;
using System;
public class SB_BinarySearchTree<T> where T : IComparable
{
public class Node
{
public T Value;
public Node LChild;
public Node RChild;
public int Count;
public Node(T v)
{
Value = v;
Count = 1;
}
}
static Random _rnd = new Random();
public static int Count(Node t)
{
return t == null ? 0 : t.Count;
}
static Node Update(Node t)
{
t.Count = Count(t.LChild) + Count(t.RChild) + 1;
return t;
}
public static Node Merge(Node l, Node r)
{
if (l == null || r == null) return l == null ? r : l;
if (Count(l) / (double)(Count(l) + Count(r)) > _rnd.NextDouble())
{
l.RChild = Merge(l.RChild, r);
return Update(l);
}
else
{
r.LChild = Merge(l, r.LChild);
return Update(r);
}
}
public static Tuple<Node, Node> Split(Node t, int k)
{
if (t == null) return new Tuple<Node, Node>(null, null);
if (k <= Count(t.LChild))
{
var s = Split(t.LChild, k);
t.LChild = s.Item2;
return new Tuple<Node, Node>(s.Item1, Update(t));
}
else
{
var s = Split(t.RChild, k - Count(t.LChild) - 1);
t.RChild = s.Item1;
return new Tuple<Node, Node>(Update(t), s.Item2);
}
}
public static Node Remove(Node t, T v)
{
if (Find(t, v) == null) return t;
return RemoveAt(t, LowerBound(t, v));
}
public static Node RemoveAt(Node t, int k)
{
var s = Split(t, k);
var s2 = Split(s.Item2, 1);
return Merge(s.Item1, s2.Item2);
}
public static bool Contains(Node t, T v)
{
return Find(t, v) != null;
}
public static Node Find(Node t, T v)
{
while (t != null)
{
var cmp = t.Value.CompareTo(v);
if (cmp > 0) t = t.LChild;
else if (cmp < 0) t = t.RChild;
else break;
}
return t;
}
public static Node FindByIndex(Node t, int idx)
{
if (t == null) return null;
var currentIdx = Count(t) - Count(t.RChild) - 1;
while (t != null)
{
if (currentIdx == idx) return t;
if (currentIdx > idx)
{
t = t.LChild;
currentIdx -= (Count(t == null ? null : t.RChild) + 1);
}
else
{
t = t.RChild;
currentIdx += (Count(t == null ? null : t.LChild) + 1);
}
}
return null;
}
public static int UpperBound(Node t, T v)
{
var torg = t;
if (t == null) return -1;
var ret = int.MaxValue;
var idx = Count(t) - Count(t.RChild) - 1;
while (t != null)
{
var cmp = t.Value.CompareTo(v);
if (cmp > 0)
{
ret = Min(ret, idx);
t = t.LChild;
idx -= (Count(t == null ? null : t.RChild) + 1);
}
else if (cmp <= 0)
{
t = t.RChild;
idx += (Count(t == null ? null : t.LChild) + 1);
}
}
return ret == int.MaxValue ? Count(torg) : ret;
}
public static int LowerBound(Node t, T v)
{
var torg = t;
if (t == null) return -1;
var idx = Count(t) - Count(t.RChild) - 1;
var ret = int.MaxValue;
while (t != null)
{
var cmp = t.Value.CompareTo(v);
if (cmp >= 0)
{
if (cmp == 0) ret = Min(ret, idx);
t = t.LChild;
if (t == null) ret = Min(ret, idx);
idx -= t == null ? 0 : (Count(t.RChild) + 1);
}
else if (cmp < 0)
{
t = t.RChild;
idx += (Count(t == null ? null : t.LChild) + 1);
if (t == null) return idx;
}
}
return ret == int.MaxValue ? Count(torg) : ret;
}
public static Node Insert(Node t, T v)
{
var ub = LowerBound(t, v);
return InsertByIdx(t, ub, v);
}
static Node InsertByIdx(Node t, int k, T v)
{
var s = Split(t, k);
return Merge(Merge(s.Item1, new Node(v)), s.Item2);
}
public static IEnumerable<T> Enumerate(Node t)
{
var ret = new List<T>();
Enumerate(t, ret);
return ret;
}
static void Enumerate(Node t, List<T> ret)
{
if (t == null) return;
Enumerate(t.LChild, ret);
ret.Add(t.Value);
Enumerate(t.RChild, ret);
}
}
public class Set<T> where T : IComparable
{
protected SB_BinarySearchTree<T>.Node _root;
public T this[int idx] { get { return ElementAt(idx); } }
public int Count()
{
return SB_BinarySearchTree<T>.Count(_root);
}
public virtual void Insert(T v)
{
if (_root == null) _root = new SB_BinarySearchTree<T>.Node(v);
else
{
if (SB_BinarySearchTree<T>.Find(_root, v) != null) return;
_root = SB_BinarySearchTree<T>.Insert(_root, v);
}
}
public void Clear()
{
_root = null;
}
public void Remove(T v)
{
_root = SB_BinarySearchTree<T>.Remove(_root, v);
}
public bool Contains(T v)
{
return SB_BinarySearchTree<T>.Contains(_root, v);
}
public T ElementAt(int k)
{
var node = SB_BinarySearchTree<T>.FindByIndex(_root, k);
if (node == null) throw new IndexOutOfRangeException();
return node.Value;
}
public int Count(T v)
{
return SB_BinarySearchTree<T>.UpperBound(_root, v) - SB_BinarySearchTree<T>.LowerBound(_root, v);
}
public int LowerBound(T v)
{
return SB_BinarySearchTree<T>.LowerBound(_root, v);
}
public int UpperBound(T v)
{
return SB_BinarySearchTree<T>.UpperBound(_root, v);
}
public Tuple<int, int> EqualRange(T v)
{
if (!Contains(v)) return new Tuple<int, int>(-1, -1);
return new Tuple<int, int>(SB_BinarySearchTree<T>.LowerBound(_root, v), SB_BinarySearchTree<T>.UpperBound(_root, v) - 1);
}
public List<T> ToList()
{
return new List<T>(SB_BinarySearchTree<T>.Enumerate(_root));
}
}
public class MultiSet<T> : Set<T> where T : IComparable
{
public override void Insert(T v)
{
if (_root == null) _root = new SB_BinarySearchTree<T>.Node(v);
else _root = SB_BinarySearchTree<T>.Insert(_root, v);
}
}
public class P : IComparable
{
public int id { get; set; }
public int rate { get; set; }
public int CompareTo(object obj)
{
var x = (P)obj;
if (this.rate > x.rate) return 1;
else if (this.rate == x.rate) return 0;
else return -1;
}
}
public class Hello
{
public static int n;
static void Main()
{
n = int.Parse(Console.ReadLine().Trim());
var a0 = Console.ReadLine().Trim();
var a1 = Console.ReadLine().Trim();
var s = new int[n];
var t = new int[n];
for (int i = 0; i < n; i++)
{
s[i] = a0[i] - '0';
t[i] = a1[i] - '0';
}
getAns(s, t);
}
static void getAns(int[] s, int[] t)
{
var set = new Set<int>();
for (int i = 0; i < n; i++)
if (s[i] != t[i]) set.Insert(i);
var q = int.Parse(Console.ReadLine().Trim());
var ans = new char[q];
for (int i = 0; i < q; i++)
{
string[] line = Console.ReadLine().Trim().Split(' ');
var x = int.Parse(line[1]) - 1;
var y = int.Parse(line[2]);
if (line[0] == "S") s[x] = y;
else t[x] = y;
if (s[x] != t[x] && !set.Contains(x)) set.Insert(x);
if (s[x] == t[x] && set.Contains(x)) set.Remove(x);
var a = set.ElementAt(0);
ans[i] = s[a] > t[a] ? '>' : '<';
}
Console.WriteLine(string.Join("\n", ans));
}
}