結果

問題 No.2796 Small Matryoshka
ユーザー KumaTachiRenKumaTachiRen
提出日時 2024-06-28 21:51:12
言語 C#
(.NET 8.0.203)
結果
AC  
実行時間 224 ms / 2,000 ms
コード長 12,957 bytes
コンパイル時間 8,806 ms
コンパイル使用メモリ 167,584 KB
実行使用メモリ 203,380 KB
最終ジャッジ日時 2024-06-28 21:51:24
合計ジャッジ時間 12,193 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 43 ms
23,668 KB
testcase_01 AC 41 ms
23,936 KB
testcase_02 AC 41 ms
23,552 KB
testcase_03 AC 39 ms
23,680 KB
testcase_04 AC 40 ms
23,936 KB
testcase_05 AC 71 ms
31,104 KB
testcase_06 AC 121 ms
43,636 KB
testcase_07 AC 39 ms
23,668 KB
testcase_08 AC 109 ms
40,704 KB
testcase_09 AC 224 ms
45,556 KB
testcase_10 AC 118 ms
32,896 KB
testcase_11 AC 149 ms
37,376 KB
testcase_12 AC 89 ms
29,568 KB
testcase_13 AC 71 ms
29,312 KB
testcase_14 AC 84 ms
29,568 KB
testcase_15 AC 74 ms
29,184 KB
testcase_16 AC 78 ms
29,440 KB
testcase_17 AC 191 ms
39,936 KB
testcase_18 AC 204 ms
41,344 KB
testcase_19 AC 122 ms
33,280 KB
testcase_20 AC 134 ms
34,688 KB
testcase_21 AC 178 ms
203,380 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (82 ms)。
MSBuild のバージョン 17.9.6+a4ecab324 (.NET)
/home/judge/data/code/Main.cs(60,1392): warning CS8632: '#nullable' 注釈コンテキスト内のコードでのみ、Null 許容参照型の注釈を使用する必要があります。 [/home/judge/data/code/main.csproj]
/home/judge/data/code/Main.cs(60,1593): warning CS8632: '#nullable' 注釈コンテキスト内のコードでのみ、Null 許容参照型の注釈を使用する必要があります。 [/home/judge/data/code/main.csproj]
/home/judge/data/code/Main.cs(60,2032): warning CS8632: '#nullable' 注釈コンテキスト内のコードでのみ、Null 許容参照型の注釈を使用する必要があります。 [/home/judge/data/code/main.csproj]
/home/judge/data/code/Main.cs(60,2360): warning CS8632: '#nullable' 注釈コンテキスト内のコードでのみ、Null 許容参照型の注釈を使用する必要があります。 [/home/judge/data/code/main.csproj]
/home/judge/data/code/Main.cs(60,4149): warning CS8632: '#nullable' 注釈コンテキスト内のコードでのみ、Null 許容参照型の注釈を使用する必要があります。 [/home/judge/data/code/main.csproj]
/home/judge/data/code/Main.cs(60,4343): warning CS8632: '#nullable' 注釈コンテキスト内のコードでのみ、Null 許容参照型の注釈を使用する必要があります。 [/home/judge/data/code/main.csproj]
/home/judge/data/code/Main.cs(60,5659): warning CS8632: '#nullable' 注釈コンテキスト内のコードでのみ、Null 許容参照型の注釈を使用する必要があります。 [/home/judge/data/code/main.csproj]
/home/judge/data/code/Main.cs(60,6594): warning CS8632: '#nullable' 注釈コンテキスト内のコードでのみ、Null 許容参照型の注釈を使用する必要があります。 [/home/judge/data/code/main.csproj]
/home/judge/data/code/Mai

ソースコード

diff # 

using Lib;
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Text;
using static Lib.OutputLib;
public class Solver
{
    const bool MultiTestCase = false;
    void Solve()
    {
        int n = ri;
        ReadArray(out (int a, int b)[] ab, n, () => (ri, ri));
        Array.Sort(ab, (p1, p2) => p1.b - p2.b);

        var set = new RedBlackTree<long, long>(x => x);
        foreach (var (a, b) in ab)
        {
            long idx = set.LowerBoundKey(a + 1) - 1;
            if (idx != -1) set.RemoveAt(idx);
            set.Add(b);
        }
        Write(set.Count() - 1);
    }

#pragma warning disable CS0162
    public Solver() { if (!MultiTestCase) Solve(); else for (int t = ri; t > 0; t--) Solve(); }
#pragma warning restore CS0162

    const int IINF = 1 << 30;
    const long INF = 1L << 60;
    int ri { [MethodImpl(256)] get => (int)sc.Integer(); }
    long rl { [MethodImpl(256)] get => sc.Integer(); }
    uint rui { [MethodImpl(256)] get => (uint)sc.UInteger(); }
    ulong rul { [MethodImpl(256)] get => sc.UInteger(); }
    double rd { [MethodImpl(256)] get => sc.Double(); }
    string rs { [MethodImpl(256)] get => sc.Scan(); }
    string rline { [MethodImpl(256)] get => sc.Line(); }
    public StreamScanner sc = new StreamScanner(Console.OpenStandardInput());
    void ReadArray(out int[] a, int n) { a = new int[n]; for (int i = 0; i < a.Length; i++) a[i] = ri; }
    void ReadArray(out long[] a, int n) { a = new long[n]; for (int i = 0; i < a.Length; i++) a[i] = rl; }
    void ReadArray<T>(out T[] a, int n, Func<T> read) { a = new T[n]; for (int i = 0; i < a.Length; i++) a[i] = read(); }
}

static class Program
{
    static public void Main(string[] args)
    {
        SourceExpander.Expander.Expand();
        Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false });
        new Solver();
        Console.Out.Flush();
    }
}
#region Expanded by https://github.com/kzrnm/SourceExpander
public class RedBlackTree<TKey,TValue>:IEnumerable<TValue>{private readonly Func<TValue,TKey>_keySelector;private readonly IComparer<TKey>_keyComparer;class Node{public Node?Parent{get;set;}public Node?LChild{get;set;}public Node?RChild{get;set;}public int Color{get;set;}public long CountSum{get;set;}public long Count{get;set;}public TKey Key{get;}public TValue Value{get;}public void ReplaceChild(Node?x,Node?y=null){if(LChild==x)LChild=y;if(RChild==x)RChild=y;}public Node(TKey _key,TValue _val,long _count,Node?_par=null,int _color=0){Key=_key;Value=_val;Count=_count;CountSum=Count;Color=_color;Parent=_par;LChild=null;RChild=null;}public override string ToString()=>$"[{Parent}]->{Value}*{Count}[{Color}]->[{LChild},{RChild}]:{CountSum}";}public IEnumerator<TValue>GetEnumerator()=>ToList().GetEnumerator();IEnumerator IEnumerable.GetEnumerator()=>GetEnumerator();Node?Root;public long CountAll{get;private set;}public RedBlackTree(Func<TValue,TKey>keySelector):this(keySelector,Comparer<TKey>.Default){}public RedBlackTree(Func<TValue,TKey>keySelector,IComparer<TKey>keyComparer){_keyComparer=keyComparer;_keySelector=keySelector;Root=null;CountAll=0;}[MethodImpl(256)]public override string ToString()=>string.Join(",",ToList());List<TValue>list;[MethodImpl(256)]public List<TValue>ToList(){list=new List<TValue>();ToList(Root);return list;}[MethodImpl(256)]private void ToList(Node?x){if(x==null)return;ToList(x.LChild);for(int i=0;i<x.Count;i++)list.Add(x.Value);ToList(x.RChild);}[MethodImpl(256)]public string Debug()=>Debug(Root,"","");[MethodImpl(256)]private string Debug(Node?x,string indent,string prefix){if(x==null)return "";if(indent.Length>40)return "...";var newindent=indent+"  ";var ret="";var t=Debug(x.LChild,newindent,"/");if(t!="")ret+=t;ret+=$"{indent}{prefix}{(x.Color==0?"B":"R")}:{x.Value}*{x.Count}<{x.CountSum}";t=Debug(x.RChild,newindent,"\\");if(t!="")ret+=t;return ret;}[MethodImpl(256)]public bool Contains(TValue v)=>Contains(Root,_keySelector(v));[MethodImpl(256)]private bool Contains(Node?x,TKey k){while(true){if(x==null)return false;if(_keyComparer.Compare(k,x.Key)==0)return true;x=_keyComparer.Compare(k,x.Key)<0?x.LChild:x.RChild;}}[MethodImpl(256)]public long Count()=>Root==null?0:Root.CountSum;[MethodImpl(256)]public long Count(TValue v)=>Count(Root,_keySelector(v));[MethodImpl(256)]private long Count(Node?x,TKey k){while(true){if(x==null)return 0;if(_keyComparer.Compare(k,x.Key)==0)return x.Count;x=_keyComparer.Compare(k,x.Key)<0?x.LChild:x.RChild;}}[MethodImpl(256)]public long UpperBound(TValue v)=>UpperBoundKey(_keySelector(v));[MethodImpl(256)]public long UpperBoundKey(TKey k){if(Root==null)return 0;Node?x=Root;long ret=0;while(x!=null){if(_keyComparer.Compare(k,x.Key)<0){x=x.LChild;}else{ret+=x.Count+(x.LChild!=null?x.LChild.CountSum:0);x=x.RChild;}}return ret;}[MethodImpl(256)]public long LowerBound(TValue v)=>LowerBoundKey(_keySelector(v));[MethodImpl(256)]public long LowerBoundKey(TKey k){if(Root==null)return 0;Node?x=Root;long ret=0;while(x!=null){if(_keyComparer.Compare(k,x.Key)<=0){x=x.LChild;}else{ret+=x.Count+(x.LChild!=null?x.LChild.CountSum:0);x=x.RChild;}}return ret;}public TValue this[long i]{[MethodImpl(256)]get=>GetByIndex(i);}[MethodImpl(256)]public TValue GetByIndex(long i){if((ulong)i>=(ulong)CountAll)throw new IndexOutOfRangeException();Node?x=Root;long cnt=0;while(true){if(x==null)throw new IndexOutOfRangeException();long lcnt=x.LChild==null?0:x.LChild.CountSum;if(i<cnt+lcnt)x=x.LChild;else{cnt+=lcnt;if(i<cnt+x.Count)return x.Value;cnt+=x.Count;x=x.RChild;}}}[MethodImpl(256)]private void Rotate(Node x,int dir){if(x==null)return;Node?p=x.Parent;Node?y=dir==0?x.RChild:x.LChild;if(y==null)return;if(p==null)Root=y;else p.ReplaceChild(x,y);y.Parent=p;x.Parent=y;y.CountSum=x.CountSum;x.CountSum-=y.Count;if(dir==0){if(y.LChild!=null)y.LChild.Parent=x;x.RChild=y.LChild;y.LChild=x;if(y.RChild!=null)x.CountSum-=y.RChild.CountSum;}else{if(y.RChild!=null)y.RChild.Parent=x;x.LChild=y.RChild;y.RChild=x;if(y.LChild!=null)x.CountSum-=y.LChild.CountSum;}}[MethodImpl(256)]public TValue Max()=>MaxNode(Root).Value;[MethodImpl(256)]private Node MaxNode(Node?x){if(x==null)throw new IndexOutOfRangeException();while(x.RChild!=null)x=x.RChild;return x;}[MethodImpl(256)]public TValue Min()=>MinNode(Root).Value;[MethodImpl(256)]private Node MinNode(Node?x){if(x==null)throw new IndexOutOfRangeException();while(x.LChild!=null)x=x.LChild;return x;}[MethodImpl(256)]public void Add(TValue v,long cnt=1){if(Root==null)Root=new Node(_keySelector(v),v,cnt);else Add(Root,v,cnt);CountAll+=cnt;}[MethodImpl(256)]private void Add(Node x,TValue v,long cnt){TKey k=_keySelector(v);while(true){if(_keyComparer.Compare(k,x.Key)==0){x.Count+=cnt;Node?t=x;while(t!=null){t.CountSum+=cnt;t=t.Parent;}return;}else{int dir=_keyComparer.Compare(k,x.Key)<0?0:1;Node?c=dir==0?x.LChild:x.RChild;if(c==null){c=new Node(k,v,cnt,x,1);if(dir==0)x.LChild=c;else x.RChild=c;Node?t=x;while(t!=null){t.CountSum+=cnt;t=t.Parent;}AddFix(c);return;}x=c;}}}[MethodImpl(256)]private void AddFix(Node x){while(true){var p=x.Parent;if(p==null){x.Color=0;return;}if(p.Color==0)return;var pp=p.Parent;if(pp==null){p.Color=0;return;}int dir=pp.LChild==p?0:1;var ppc=dir==0?pp.RChild:pp.LChild;if(ppc!=null&&ppc.Color==1){p.Color=0;ppc.Color=0;pp.Color=1;x=pp;continue;}else if((dir==0)^(x==p.RChild)){pp.Color=1;p.Color=0;Rotate(pp,dir^1);return;}else{pp.Color=1;x.Color=0;Rotate(p,dir);Rotate(pp,dir^1);return;}}}[MethodImpl(256)]public void RemoveAt(long x)=>Remove(Root,GetByIndex(x),1);[MethodImpl(256)]public void Remove(TValue v,long cnt=1)=>Remove(Root,v,cnt);[MethodImpl(256)]private void Remove(Node?x,TValue v,long cnt){TKey k=_keySelector(v);while(true){if(x==null)return;if(_keyComparer.Compare(k,x.Key)==0){if(x.Count>cnt){CountAll-=cnt;x.Count-=cnt;var t=x;while(t!=null){t.CountSum-=cnt;t=t.Parent;}}else{cnt=x.Count;CountAll-=cnt;Node?p=x.Parent,l=x.LChild,r=x.RChild;var t=p;while(t!=null){t.CountSum-=cnt;t=t.Parent;}if(l==null){if(p==null)Root=r;else p.ReplaceChild(x,r);if(r!=null){r.Parent=p;r.Color=0;}}else if(r==null){if(p==null)Root=l;else p.ReplaceChild(x,l);l.Parent=p;l.Color=0;}else{Node y=MinNode(r);var z=y.RChild;if(y!=r){t=y.Parent;while(t!=x){t.CountSum-=y.Count;t=t.Parent;}y.Parent.LChild=z;if(z!=null)z.Parent=y.Parent;r.Parent=y;y.RChild=r;}y.CountSum=x.CountSum-x.Count;if(l!=null)l.Parent=y;y.LChild=l;if(p==null)Root=y;else p.ReplaceChild(x,y);y.Parent=p;y.Color=x.Color;RemoveFix(z);}x.Count=0;}return;}x=_keyComparer.Compare(k,x.Key)<0?x.LChild:x.RChild;}}[MethodImpl(256)]private void RemoveFix(Node?x){while(true){if(x==null)return;if(x==Root||x.Color==1){x.Color=0;return;}Node p=x.Parent;int dir=p.LChild==x?1:0;var s=dir==0?p.LChild:p.RChild;if(s==null)return;if(s.Color==1){p.Color=1;s.Color=0;Rotate(p,dir^1);continue;}else{Node?sl=dir==1?s.LChild:s.RChild;Node?sr=dir==0?s.LChild:s.RChild;int slc=sl==null?0:sl.Color;int src=sr==null?0:sr.Color;if(slc==0&&src==0){s.Color=1;x=p;continue;}else if(src==0){s.Color=1;sl.Color=0;Rotate(s,dir);x=sl;continue;}else{s.Color=p.Color;p.Color=0;sr.Color=0;Rotate(p,dir^1);return;}}}}}
namespace Lib{public partial class StreamScanner{public int[][]ReadUnweightedTree(int n,int origin=1){var gr=new List<int>[n];for(int i=0;i<n;i++)gr[i]=new List<int>();for(int i=0;i<n-1;i++){int u=(int)(Integer()-origin);int v=(int)(Integer()-origin);gr[u].Add(v);gr[v].Add(u);}var g=new int[n][];for(int i=0;i<n;i++)g[i]=gr[i].ToArray();return g;}}}
namespace Lib{public partial class StreamScanner{public StreamScanner(Stream stream){str=stream;}private readonly Stream str;private readonly byte[]buf=new byte[1024];private int len,ptr;public bool isEof=false;public bool IsEndOfStream{get{return isEof;}}[MethodImpl(256)]private byte Read(){if(isEof)throw new EndOfStreamException();if(ptr>=len){ptr=0;if((len=str.Read(buf,0,1024))<=0){isEof=true;return 0;}}return buf[ptr++];}[MethodImpl(256)]public char Char(){byte b=0;do b=Read();while(b<33||126<b);return(char)b;}[MethodImpl(256)]public string Line(){var sb=new StringBuilder();for(var b=Char();b!=10&&!isEof;b=(char)Read())sb.Append(b);return sb.ToString();}[MethodImpl(256)]public string Scan(){var sb=new StringBuilder();for(var b=Char();b>=33&&b<=126;b=(char)Read())sb.Append(b);return sb.ToString();}[MethodImpl(256)]public long Integer(){long ret=0;byte b=0;var ng=false;do b=Read();while(b!='-'&&(b<'0'||'9'<b));if(b=='-'){ng=true;b=Read();}for(;true;b=Read()){if(b<'0'||'9'<b)return ng?-ret:ret;else ret=ret*10+b-'0';}}[MethodImpl(256)]public ulong UInteger(){ulong ret=0;byte b=0;do b=Read();while(b<'0'||'9'<b);for(;true;b=Read()){if(b<'0'||'9'<b)return ret;else ret=ret*10+b-'0';}}[MethodImpl(256)]public double Double()=>double.Parse(Scan());}}
namespace Lib{public static class OutputLib{[MethodImpl(256)]public static void WriteJoin<T>(string s,IEnumerable<T>t)=>Console.WriteLine(string.Join(s,t));[MethodImpl(256)]public static void WriteMat<T>(T[,]a,string sep=" "){int sz1=a.GetLength(0),sz2=a.GetLength(1);var b=new T[sz2];for(int i=0;i<sz1;i++){for(int j=0;j<sz2;j++)b[j]=a[i,j];WriteJoin(sep,b);}}[MethodImpl(256)]public static void WriteMat<T>(T[][]a,string sep=" "){for(int i=0;i<a.Length;i++)WriteJoin(sep,a[i]);}[MethodImpl(256)]public static void WriteMat<T>(T[][]a,Func<T,string>map,string sep=" "){for(int i=0;i<a.Length;i++)WriteJoin(sep,a[i].Select(x=>map(x)));}[MethodImpl(256)]public static void Write(object t)=>Console.WriteLine(t.ToString());[MethodImpl(256)]public static void Write(params object[]arg)=>Console.WriteLine(string.Join(" ",arg.Select(x=>x.ToString())));[MethodImpl(256)]public static void Write(string str)=>Console.WriteLine(str);[MethodImpl(256)]public static void WriteFlush(object t){Console.WriteLine(t.ToString());Console.Out.Flush();}[MethodImpl(256)]public static void WriteError(object t)=>Console.Error.WriteLine(t.ToString());[MethodImpl(256)]public static void Flush()=>Console.Out.Flush();[MethodImpl(256)]public static void YN(bool t)=>Console.WriteLine(t?"YES":"NO");[MethodImpl(256)]public static void Yn(bool t)=>Console.WriteLine(t?"Yes":"No");[MethodImpl(256)]public static void yn(bool t)=>Console.WriteLine(t?"yes":"no");[MethodImpl(256)]public static void DeleteLine()=>Console.Write("\x1b[1A\x1b[2K");[MethodImpl(256)]public static void ProgressBar(long now,long total,int blocks=50){int x=(int)((2*now*blocks+1)/(2*total));Console.Write($"\x1b[G[\x1b[42m{string.Concat(Enumerable.Repeat("_",x))}\x1b[0m{string.Concat(Enumerable.Repeat("_",blocks-x))}] : {now} / {total}");}}}
namespace SourceExpander{public class Expander{[Conditional("EXP")]public static void Expand(string inputFilePath=null,string outputFilePath=null,bool ignoreAnyError=true){}public static string ExpandString(string inputFilePath=null,bool ignoreAnyError=true){return "";}}}
#endregion Expanded by https://github.com/kzrnm/SourceExpander
0