結果

問題 No.686 Uncertain LIS
ユーザー 紙ぺーぱー
提出日時 2018-05-12 00:38:41
言語 C#(csc)
(csc 3.9.0)
結果
MLE  
実行時間 -
コード長 11,431 bytes
コンパイル時間 2,545 ms
コンパイル使用メモリ 115,552 KB
実行使用メモリ 825,844 KB
最終ジャッジ日時 2024-06-28 09:23:20
合計ジャッジ時間 5,663 ms
ジャッジサーバーID
(参考情報)
judge4 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 3 MLE * 1 -- * 32
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff #
プレゼンテーションモードにする

using System;
using System.Linq;
using System.Collections.Generic;
using Debug = System.Diagnostics.Debug;
using SB = System.Text.StringBuilder;
//using System.Numerics;
using static System.Math;
namespace Program {
public class Solver {
Random rnd = new Random(0);
public void Solve() {
var n = ri;
var seg = new BalancedTree();
seg.Insert(0, 0);
seg.Insert(1, 1000000000);
/*
n = 75;
var dp = new long[100];
//*/
for (int i = 0; i < n; i++)
{
var l = ri; var r = ri;
/*
var l = rnd.Next(1, 100);
var r = rnd.Next(1, 100);
if (l > r) Swap(ref l, ref r);
for (int j = r; j >= l; j--)
dp[j] = Math.Max(dp[j], dp[j - 1] + 1);
for (int j = 1; j < 100; j++)
dp[j] = Math.Max(dp[j], dp[j - 1]);
//*/
var lb = seg.tree.root.LowerBound(l, Comparer<long>.Default);
var rb = seg.tree.root.LowerBound(r, Comparer<long>.Default);
//Debug.WriteLine($"{l} {r} {lb} {rb}");
if (lb != rb)
{
seg.Push(lb, rb, 1);
seg.RemoveAt(rb);
seg.Insert(lb, l);
}
else
{
seg.RemoveAt(lb); seg.Insert(lb, l);
}
Debug.WriteLine(seg.Items.AsJoinedString());
}
var a = seg.Items;
Debug.WriteLine(a.AsJoinedString());
for (int i = a.Length - 1; i >= 0; i--)
if (a[i] != 1000000000) { Console.WriteLine(i); break; }
//Debug.WriteLine(dp.Max());
}
const long INF = 5L << 60;
static int[] dx = { -1, 0, 1, 0 };
static int[] dy = { 0, 1, 0, -1 };
int ri { get { return sc.Integer(); } }
long rl { get { return sc.Long(); } }
double rd { get { return sc.Double(); } }
string rs { get { return sc.Scan(); } }
public IO.StreamScanner sc = new IO.StreamScanner(Console.OpenStandardInput());
static T[] Enumerate<T>(int n, Func<int, T> f) {
var a = new T[n];
for (int i = 0; i < n; ++i) a[i] = f(i);
return a;
}
static public void Swap<T>(ref T a, ref T b) { var tmp = a; a = b; b = tmp; }
}
}
#region main
static class Ex {
static public string AsString(this IEnumerable<char> ie) { return new string(ie.ToArray()); }
static public string AsJoinedString<T>(this IEnumerable<T> ie, string st = " ") {
return string.Join(st, ie);
}
static public void Main() {
Console.SetOut(new Program.IO.Printer(Console.OpenStandardOutput()) { AutoFlush = false });
var solver = new Program.Solver();
solver.Solve();
Console.Out.Flush();
}
}
#endregion
#region Ex
namespace Program.IO {
using System.IO;
using System.Text;
using System.Globalization;
public class Printer: StreamWriter {
public override IFormatProvider FormatProvider { get { return CultureInfo.InvariantCulture; } }
public Printer(Stream stream) : base(stream, new UTF8Encoding(false, true)) { }
}
public class StreamScanner {
public StreamScanner(Stream stream) { str = stream; }
public readonly Stream str;
private readonly byte[] buf = new byte[1024];
private int len, ptr;
public bool isEof = false;
public bool IsEndOfStream { get { return isEof; } }
private byte read() {
if (isEof) return 0;
if (ptr >= len)
{
ptr = 0;
if ((len = str.Read(buf, 0, 1024)) <= 0)
{
isEof = true;
return 0;
}
}
return buf[ptr++];
}
public char Char() {
byte b = 0;
do b = read(); while ((b < 33 || 126 < b) && !isEof);
return (char)b;
}
public string Scan() {
var sb = new StringBuilder();
for (var b = Char(); b >= 33 && b <= 126; b = (char)read()) sb.Append(b);
return sb.ToString();
}
public string ScanLine() {
var sb = new StringBuilder();
for (var b = Char(); b != '\n' && b != 0; b = (char)read()) if (b != '\r') sb.Append(b);
return sb.ToString();
}
public long Long() { return isEof ? long.MinValue : long.Parse(Scan()); }
public int Integer() { return isEof ? int.MinValue : int.Parse(Scan()); }
public double Double() { return isEof ? double.NaN : double.Parse(Scan(), CultureInfo.InvariantCulture); }
}
}
#endregion
#region Balanced Tree
public class BalancedTree {
public AVLTree<Node> tree = new AVLTree<Node>();
public int Count { get { return tree.Count; } }
public void Push(int l, int r, long v) {
push(tree.root, l, r, v);
}
Node push(Node n, int l, int r, long v) {
n = n.Push();
if (l <= 0 && n.cnt <= r)
{
n.Add += v;
n.Update();
return n;
}
else
{
if (0 < r && l < n.lst.cnt) n.lst = push(n.lst, l, r, v);
if (n.lst.cnt + 1 < r && l < n.cnt) n.rst = push(n.rst, l - n.lst.cnt - 1, r - n.lst.cnt - 1, v);
if (l <= n.lst.cnt && n.lst.cnt < r) n.Key += v;
n.Update();
return n;
}
}
public long Query(int l, int r) {
return query(tree.root, l, r);
}
long query(Node n, int l, int r) {
n = n.Push();
if (l <= 0 && n.cnt <= r)
{
return n.Key;
}
else
{
if (0 < r && l < n.lst.cnt) return query(n.lst, l, r);
else if (n.lst.cnt + 1 < r && l < n.cnt) return query(n.rst, l - n.lst.cnt - 1, r - n.lst.cnt - 1);
else return n.Key;
}
}
public bool Insert(int lb, long item) {
var v = new Node() { Key = item };
tree.Insert(v, lb);
return true;
}
public bool RemoveAt(int k) {
if (k < 0 || k >= Count) return false;
tree.RemoveAt(k);
return true;
}
public long this[int index] {
get {
if (index < 0 || index >= Count) throw new IndexOutOfRangeException();
var t = tree.Find(tree.root, index);
return t.Key;
}
}
public long[] Items {
get {
var ret = new long[Count];
int ptr = 0;
walk(tree.root, ret, ref ptr);
return ret;
}
}
void walk(Node root, long[] a, ref int ptr) {
if (root.cnt == 0) return;
walk(root.lst, a, ref ptr);
a[ptr++] = root.Key;
walk(root.rst, a, ref ptr);
}
public class Node: AVLTreeNode<Node>, IKey<long> {
public long Key { get; set; }
public long Add { get; set; }
public override Node Push() {
if (lst.cnt != 0)
lst.Add += Add;
if (rst.cnt != 0)
rst.Add += Add;
Key += Add;
Add = 0;
return this;
}
}
}
#endregion
#region AVLTree
public abstract class AVLTreeNode<T>: BinaryTreeNode<T>
where T : AVLTreeNode<T> {
public int rank;
public override void Update() {
cnt = 1 + lst.cnt + rst.cnt;
rank = 1 + Math.Max(lst.rank, rst.rank);
}
}
public class AVLTree<T>: Tree<T>
where T : AVLTreeNode<T>, new() {
public override void Insert(T v, int k) { root = insert(root, v, k); NIL.cnt = 0; }
public override void RemoveAt(int k) { root = removeat(root, k); NIL.cnt = 0; }
T insert(T t, T v, int k) {
t = t.Push();
if (t.cnt == 0)
{
v.lst = v.rst = NIL;
v.Update();
return v;
}
if (t.lst.cnt >= k)
t.lst = insert(t.lst, v, k);
else
t.rst = insert(t.rst, v, k - t.lst.cnt - 1);
if (t.lst.rank - t.rst.rank == -2)
{
if (t.rst.lst.rank > t.rst.rst.rank) t.rst = rotR(t.rst);
t = rotL(t);
}
else if (t.lst.rank - t.rst.rank == 2)
{
if (t.lst.lst.rank < t.lst.rst.rank) t.lst = rotL(t.lst);
t = rotR(t);
}
else t.Update();
t.Update();
return t;
}
T removeat(T t, int k) {
t = t.Push();
var cnt = t.lst.cnt;
if (cnt < k) t.rst = removeat(t.rst, k - cnt - 1);
else if (cnt > k) t.lst = removeat(t.lst, k);
else
{
if (cnt == 0) return t.rst;
if (t.rst.cnt == 0) return t.lst;
var next = Find(t.lst, k - 1);
next = next.Push();
next.lst = removeat(t.lst, k - 1);
next.rst = t.rst;
t = next;
}
if (t.lst.rank - t.rst.rank == -2)
{
if (t.rst.lst.rank > t.rst.rst.rank) t.rst = rotR(t.rst);
t = rotL(t);
}
else if (t.lst.rank - t.rst.rank == 2)
{
if (t.lst.lst.rank < t.lst.rst.rank) t.lst = rotL(t.lst);
t = rotR(t);
}
else t.Update();
return t;
}
}
#endregion
#region BinaryTree
public interface IKey<K> { K Key { get; set; } }
public abstract class BinaryTreeNode<T>
where T : BinaryTreeNode<T> {
public int cnt;
public T lst, rst;
public abstract T Push();
public abstract void Update();
}
public abstract class Tree<TNode>
where TNode : BinaryTreeNode<TNode>, new() {
public Tree() { NIL = new TNode(); NIL.lst = NIL; NIL.rst = NIL; root = NIL; }
public readonly TNode NIL;
public TNode root;
public int Count { get { return root.cnt; } }
protected TNode rotR(TNode t) {
t = t.Push();
var l = t.lst.Push();
t.lst = l.rst;
l.rst = t;
t.Update();
l.Update();
return l;
}
protected TNode rotL(TNode t) {
t = t.Push();
var r = t.rst.Push();
t.rst = r.lst;
r.lst = t;
r.lst = t;
t.Update();
r.Update();
return r;
}
public TNode Find(TNode t, int k) {
t = t.Push();
if (k < t.lst.cnt) return Find(t.lst, k);
else if (k > t.lst.cnt) return Find(t.rst, k - t.lst.cnt - 1);
else return t;
}
public abstract void Insert(TNode v, int k);
public abstract void RemoveAt(int k);
}
public static class TreeOperation {
static public int LowerBound<T, K>
(this T t, K k, IComparer<K> cmp)
where T : BinaryTreeNode<T>, IKey<K> {
if (t.cnt == 0) return 0;
t = t.Push();
if (cmp.Compare(k, t.Key) <= 0) return LowerBound(t.lst, k, cmp);
else return 1 + t.lst.cnt + LowerBound(t.rst, k, cmp);
}
static public int UpperBound<T, K>
(this T t, K k, IComparer<K> cmp)
where T : BinaryTreeNode<T>, IKey<K> {
if (t.cnt == 0) return 0;
t = t.Push();
if (cmp.Compare(t.Key, k) <= 0) return 1 + t.lst.cnt + UpperBound(t.rst, k, cmp);
else return UpperBound(t.lst, k, cmp);
}
}
#endregion
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0