結果

問題 No.1715 Dinner 2
ユーザー fgwiebfaoish
提出日時 2021-10-24 01:55:39
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 177 ms / 2,000 ms
コード長 11,538 bytes
コンパイル時間 1,248 ms
コンパイル使用メモリ 122,796 KB
実行使用メモリ 33,708 KB
最終ジャッジ日時 2024-10-01 10:18:43
合計ジャッジ時間 5,872 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 38
権限があれば一括ダウンロードができます
コンパイルメッセージ
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.Collections.Generic;
using System.Collections;
using System.Collections.Specialized;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.IO;
using System.Reflection;
using static System.Math;
using System.Numerics;
using System.Threading;
using System.Runtime.CompilerServices;
using System.Diagnostics;
using nint=System.Int64;
static class Program{
    const int mod=(int)1e9+7;
    static void Main(){
        Sc sc=new Sc();
        var (n,d)=sc.Tp2<int>();
        var avl=new Avl(true,true);
        var inf=long.MaxValue/3000;
        for(int i = 0;i<n;i++) {
            var e=sc.La;
            avl.Ud(-e[0]*2000-i,e[1]-e[0]);
        }
        long lb = -inf, ub = 10, mid = 0;
        while(lb+1!=ub) {
            mid=(ub+lb)/2;
            if(!Fu(mid)) { ub=mid; }
            else { lb=mid; }
        }
        bool Fu(long m) {
            var pa=new long[2];
            var za=new long[2];
            var ca=new long[]{-inf,-inf};
            for(int i = 0;i<d;i++) {
                var li=new List<(Avl.Nd e,long z,long p)>();
                for(int j = 0;j<2;j++) {
                    if(pa[j]==inf){continue;}
                    var e=Fu1(pa[j],ca[j]);
                    li.Add((e,Min(za[j],pa[j]+e.n/2000),pa[j]+e.d));
                    e=Fu2(pa[j],ca[j],e.n);
                    li.Add((e,Min(za[j],pa[j]+e.n/2000),pa[j]+e.d));
                }
                li=li.OrderByDescending(x=>x.e!=avl.du).ThenByDescending(x=>x.p).ToList();
                if(li[0].e==avl.du){return false;}
                ca[0]=li[0].e.n;
                za[0]=li[0].z;
                pa[0]=li[0].p;
                pa[1]=inf;
                for(int j = 1;j<li.Count;j++) {
                    if(li[j].e!=avl.du&&li[j].e.n!=ca[0]){
                        ca[1]=li[j].e.n;
                        za[1]=li[j].z;
                        pa[1]=li[j].p;
                        break;
                    }
                }
            }
            return za[0]>=m;
            Avl.Nd Fu1(long p,long g) {
                var e=avl.Rd((m-p)*2000-1999,g-1);
                var f=avl.Rd(Max((m-p)*2000-1999,g+1),inf);
                if(e.d<f.d){e=f;}
                return e;
            }
            Avl.Nd Fu2(long p,long g,long h) {
                if(g>h){(g,h)=(h,g);}
                var e=avl.Rd((m-p)*2000-1999,g-1);
                var f=avl.Rd(Max((m-p)*2000-1999,g+1),h-1);
                var r=avl.Rd(Max((m-p)*2000-1999,h+1),inf);
                if(e.d<f.d){e=f;}
                if(e.d<r.d){e=r;}
                return e;
            }
        }
        Console.WriteLine("{0}",lb);
    }
}
public class Avl{
    public class Nd{
        public int h=1,c=1;
        public readonly nint n;
        public long d;
        public Nd l,r,nx;
        public Nd(nint n,long d,Nd du){this.n=n;this.d=d;nx=this;l=du;r=du;}
        public override string ToString()=>"n:"+n.ToString()+" d:"+d.ToString();
    }
    private Func<long,long,bool> compare;
    private Action<Nd> compare2;
    public Nd root,du;
    public int cnt=0;
    public bool bb;
    public Avl(bool bo,bool bb){
        if(bo){
            du=new Nd(nint.MinValue>>1,long.MinValue>>1,du);
            compare=CoMax;
            compare2=CoMax;
        }
        else{
            du=new Nd(nint.MinValue>>1,long.MaxValue>>1,du);
            compare=CoMin;
            compare2=CoMin;
        }
        this.bb=bb;
        du.h=0;du.c=0;
        root=du;
    }
    public Avl(Avl z){
        if(z.du.d==long.MinValue){
            du=new Nd(nint.MinValue>>1,long.MinValue>>1,du);
            compare=CoMax;
            compare2=CoMax;
        }
        else{
            du=new Nd(nint.MinValue>>1,long.MaxValue>>1,du);
            compare=CoMin;
            compare2=CoMin;
        }
        bb=z.bb;
        du.h=0;du.c=0;
        root=Fu(z.root);
        cnt=z.cnt;
        Nd Fu(Nd nd){
            if(nd.h==0){return du;}
            Nd mn=new Nd(nd.n,nd.d,du);
            mn.h=nd.h;
            mn.c=nd.c;
            mn.l=Fu(nd.l);
            mn.r=Fu(nd.r);
            compare2(mn);
            return mn;
        }
    }
    private bool CoMax(long a,long b){return a>=b;}
    private bool CoMin(long a,long b){return a<=b;}
    private void CoMax(Nd t){
        t.nx=t;
        if(t.nx.d<t.l.nx.d){t.nx=t.l.nx;}
        if(t.nx.d<t.r.nx.d){t.nx=t.r.nx;}
    }
    private void CoMin(Nd t){
        t.nx=t;
        if(t.nx.d>t.l.nx.d){t.nx=t.l.nx;}
        if(t.nx.d>t.r.nx.d){t.nx=t.r.nx;}
    }
    public void Ud(nint n,long d){
        if(root==du){root=new Nd(n,d,du);cnt++;}
        else if(root.n==n){
            if(bb){root.d+=d;}
            else{root.d=d;}
            compare2(root);
        }
        else if(Fu(root,n,d)){
            if(Abs(root.l.h-root.r.h)>1){root=Rotate(root);}
            cnt++;
        }
    }
    private bool Fu(Nd t,nint n,long d){
        bool bo=false;
        if(t.n>n){
            if(t.l!=du){
                if(t.l.n==n){
                    if(bb){t.l.d+=d;}
                    else{t.l.d=d;}
                    compare2(t.l);
                }
                else if(bo=Fu(t.l,n,d)){
                    t.c++;
                    if(Abs(t.l.l.h-t.l.r.h)>1){t.l=Rotate(t.l);}
                    t.h=Max(t.l.h,t.r.h)+1;
                }
                compare2(t);
            }
            else{
                t.l=new Nd(n,d,du);
                bo=true;
                t.c++;
                t.h=Max(t.l.h,t.r.h)+1;
                t.nx=compare(t.nx.d,t.l.d)?t.nx:t.l;
            }
        }
        else{
            if(t.r!=du){
                if(t.r.n==n){
                    if(bb){t.r.d+=d;}
                    else{t.r.d=d;}
                    compare2(t.r);
                }
                else if(bo=Fu(t.r,n,d)){
                    t.c++;
                    if(Abs(t.r.l.h-t.r.r.h)>1){t.r=Rotate(t.r);}
                    t.h=Max(t.l.h,t.r.h)+1;
                }
                compare2(t);
            }
            else{
                t.r=new Nd(n,d,du);
                bo=true;
                t.c++;
                t.h=Max(t.l.h,t.r.h)+1;
                t.nx=compare(t.nx.d,t.r.d)?t.nx:t.r;
            }
        }
        return bo;
    }
    private Nd Rotate(Nd t){
        Nd nd=du;
        if(t.l.h>t.r.h){
            if(t.l.l.h>t.l.r.h){
                nd=t.l;t.l=t.l.r;nd.r=t;
                Ft(t);
            }
            else{
                nd=t.l.r;
                t.l.r=nd.l;nd.l=t.l;
                Ft(t.l);
                t.l=nd.r;nd.r=t;
                Ft(t);
            }
        }
        else{
            if(t.r.l.h>t.r.r.h){
                nd=t.r.l;
                t.r.l=nd.r;nd.r=t.r;
                Ft(t.r);
                t.r=nd.l;nd.l=t;
                Ft(t);
            }
            else{
                nd=t.r;t.r=t.r.l;nd.l=t;
                Ft(t);
            }
        }
        Ft(nd);
        return nd;
    }
    private void Ft(Nd t){
        t.h=Max(t.l.h,t.r.h)+1;
        t.c=t.l.c+t.r.c+1;
        compare2(t);
    }
    public bool Dl(nint n){
        if(cnt==0){return false;}
        Nd t=root;
        if(t.n==n){
            root=Fd2(root);
            if(cnt==0){return true;}
            else if(Abs(root.l.h-root.r.h)>1){root=Rotate(root);}
            else{Ft(root);}
            return true;
        }
        bool bo=Fd1(root,n);
        if(Abs(root.l.h-root.r.h)>1){root=Rotate(root);}
        else{Ft(root);}
        return bo;
    }
    private bool Fd1(Nd t,nint n){
        if(t.n>n){
            if(t.l==du){return false;}
            else if(t.l.n!=n){
                bool bo=Fd1(t.l,n);
                if(Abs(t.l.l.h-t.l.r.h)>1){t.l=Rotate(t.l);}
                else{Ft(t.l);}
                return bo;
            }
            else{
                t.l=Fd2(t.l);
                Ft(t);
                return true;
            }
        }
        else{
            if(t.r==du){return false;}
            else if(t.r.n!=n){
                bool bo=Fd1(t.r,n);
                if(Abs(t.r.l.h-t.r.r.h)>1){t.r=Rotate(t.r);}
                else{Ft(t.r);}
                return bo;
            }
            else{
                t.r=Fd2(t.r);
                Ft(t);
                return true;
            }
        }
    }
    private Nd Fd2(Nd dn){
        cnt--;
        if(dn.l==du){return dn.r;}
        if(dn.r==du){return dn.l;}
        Nd u=dn.l;
        if(u.r==du){
            u.r=dn.r;
            Ft(u);
            return u;
        }
        u=Fd3(u,dn);
        if(Abs(dn.l.l.h-dn.l.r.h)>1){u.l=Rotate(dn.l);}
        else{Ft(dn.l);}
        Ft(u);
        return u;
    }
    private Nd Fd3(Nd u,Nd dn){
        if(u.r.r!=du){
            Nd v=Fd3(u.r,dn);
            if(Abs(u.r.l.h-u.r.r.h)>1){u.r=Rotate(u.r);}
            else{Ft(u.r);}
            return v;
        }
        else{
            Nd v=u.r;u.r=u.r.l;v.l=dn.l;v.r=dn.r;
            return v;
        }
    }
    public Nd Hs(nint n){
        Nd t=root;
        if(cnt==0){return du;}
        if(t.n==n){return t;}
        Nd a=du;
        while(true){
            if(t.n>n){
                if(t.l==du){break;}
                else if(t.l.n!=n){t=t.l;}
                else{a=t.l;break;}
            }
            else{
                if(t.r==du){break;}
                else if(t.r.n!=n){t=t.r;}
                else{a=t.r;break;}
            }
        }
        return a;
    }
    public Nd Ra(int n){return cnt>=n&&cnt!=0?Fr(root,n):du;}
    private Nd Fr(Nd t,int n){
        if(t.l.c>n-1){return Fr(t.l,n);}
        if(t.l.c<n-1){return Fr(t.r,n-t.l.c-1);}
        return t;
    }
    public Nd Lb(nint n){return cnt!=0?Flb(root,n):du;}
    private Nd Flb(Nd t,nint n){
        if(t.n<n){
            if(t.r==du){return du;}
            return Flb(t.r,n);
        }
        if(t.n>n){
            if(t.l==du){return t;}
            Nd u=Flb(t.l,n);
            return u==du?t:u;
        }
        return t;
    }
    public Nd Ub(nint n){return cnt!=0?Fub(root,n):du;}
    private Nd Fub(Nd t,nint n){
        if(t.n>n){
            if(t.l==du){return du;}
            return Fub(t.l,n);
        }
        if(t.n<n){
            if(t.r==du){return t;}
            Nd u=Fub(t.r,n);
            return u==du?t:u;
        }
        return t;
    }
    public int Rg(nint a,nint b){return cnt!=0?Frg(root,a,b,false,false):0;}
    private int Frg(Nd t,nint a,nint b,bool l,bool r){
        if(t.h==0){return 0;}
        if(l&&r){return t.c;}
        if(t.n<a){return Frg(t.r,a,b,t.n>=a,r);}
        if(t.n>b){return Frg(t.l,a,b,l,t.n<=b);}
        return Frg(t.l,a,b,l,t.n<=b)+Frg(t.r,a,b,t.n>=a,r)+1;
    }
    public Nd Rd(nint a,nint b){return cnt!=0?Frd(root,a,b,false,false):du;}
    private Nd Frd(Nd t,nint a,nint b,bool l,bool r){
        if(t.h==0){return du;}
        if(l&&r){return t.nx;}
        if(t.n<a){return Frd(t.r,a,b,t.n>=a,r);}
        if(t.n>b){return Frd(t.l,a,b,l,t.n<=b);}
        var e1=Frd(t.l,a,b,l,t.n<=b);
        var e2=Frd(t.r,a,b,t.n>=a,r);
        e1=compare(e1.d,e2.d)?e1:e2;
        return compare(t.d,e1.d)?t:e1;
    }
    public Nd Gl(nint a,nint b,long d){return cnt==0?du:Fgl(root,a,b,d);}
    private Nd Fgl(Nd t,nint a,nint b,long d){
        Nd p=du;
        if(a<=t.n&&t.n<=b&&compare(t.d,d)){p=t;}
        if(a<=t.n&&compare(t.l.nx.d,d)){
            var z=Fgl(t.l,a,b,d);
            if(z!=du){p=z;}
        }
        if(p==du&&t.n<=b&&compare(t.r.nx.d,d)){p=Fgl(t.r,a,b,d);}
        return p;
    }
    public Nd Gr(nint a,nint b,long d){return cnt==0?du:Fgr(root,a,b,d);}
    private Nd Fgr(Nd t,nint a,nint b,long d){
        Nd p=du;
        if(a<=t.n&&t.n<=b&&compare(t.d,d)){p=t;}
        if(t.n<=b&&compare(t.r.nx.d,d)){
            var z=Fgr(t.r,a,b,d);
            if(z!=du){p=z;}
        }
        if(p==du&&a<=t.n&&compare(t.l.nx.d,d)){p=Fgr(t.l,a,b,d);}
        return p;
    }
    public void En(Action<Nd> f){if(cnt>0){Fen(root,f);}}
    private void Fen(Nd t,Action<Nd> f){
        f(t);
        if(t.l!=du){Fen(t.l,f);}
        if(t.r!=du){Fen(t.r,f);}
    }
}
public class Sc{
    public int I{get{return int.Parse(Console.ReadLine());}}
    public long L{get{return long.Parse(Console.ReadLine());}}
    public double D{get{return double.Parse(Console.ReadLine());}}
    public string S{get{return Console.ReadLine();}}
    public int[] Ia{get{return Array.ConvertAll(Console.ReadLine().Split(),int.Parse);}}
    public long[] La{get{return Array.ConvertAll(Console.ReadLine().Split(),long.Parse);}}
    public double[] Da{get{return Array.ConvertAll(Console.ReadLine().Split(),double.Parse);}}
    public string[] Sa{get{return Console.ReadLine().Split();}}
    public object[] Oa{get{return Console.ReadLine().Split();}}
    public int[] Ia2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),int.Parse);}}
    public int[] Ia3(string a,string b){return Array.ConvertAll((a+Console.ReadLine()+b).Split(),int.Parse);}
    public int[] Ia3(int a){return Array.ConvertAll((Console.ReadLine()+" "+a.ToString()).Split(),int.Parse);}
    public long[] La2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),long.Parse);}}
    public long[] La3(string a,string b){return Array.ConvertAll((a+Console.ReadLine()+b).Split(),long.Parse);}
    public long[] La3(int a){return Array.ConvertAll((Console.ReadLine()+" "+a.ToString()).Split(),long.Parse);}
    public double[] Da2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),double.Parse);}}
    public double[] Da3(string a,string b){return Array.ConvertAll((a+Console.ReadLine()+b).Split(),double.Parse);}
    public T[] Arr<T>(int n,Func<T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f();}return a;}
    public T[] Arr<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;}
    public T[] Arr<T>(int n,Func<string[],T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(Console.ReadLine().Split());}return a;}
    public T[] Arr<T>(int n,Func<int,string[],T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(i,Console.ReadLine().Split());}return a;}
    public (T,T) Tp2<T>(){var s=Console.ReadLine().Split();return (Ct<T>(s[0]),Ct<T>(s[1]));}
    public (T,T,T) Tp3<T>(){var s=Console.ReadLine().Split();return (Ct<T>(s[0]),Ct<T>(s[1]),Ct<T>(s[2]));}
    public (T,T,T,T) Tp4<T>(){var s=Console.ReadLine().Split();return (Ct<T>(s[0]),Ct<T>(s[1]),Ct<T>(s[2]),Ct<T>(s[3]));}
    public (T1,T2) Tp2<T1,T2>(){var s=Console.ReadLine().Split();return (Ct<T1>(s[0]),Ct<T2>(s[1]));}
    public (T1,T1,T2) Tp3<T1,T2>(){var s=Console.ReadLine().Split();return (Ct<T1>(s[0]),Ct<T1>(s[1]),Ct<T2>(s[2]));}
    private T Ct<T>(string s){return (T)Convert.ChangeType(s,typeof(T));}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0