結果
| 問題 |
No.860 買い物
|
| コンテスト | |
| ユーザー |
 fgwiebfaoish
|
| 提出日時 | 2022-01-25 00:42:07 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
AC
|
| 実行時間 | 437 ms / 1,000 ms |
| コード長 | 15,778 bytes |
| コンパイル時間 | 2,844 ms |
| コンパイル使用メモリ | 114,304 KB |
| 実行使用メモリ | 32,512 KB |
| 最終ジャッジ日時 | 2024-12-15 05:18:44 |
| 合計ジャッジ時間 | 8,350 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 15 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
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 long inf=long.MaxValue>>1;
const int mod=(int)1e9+7;//998244353;
static Sc sc=new Sc();
static Pt pt=new Pt();
static void Main(){
Solve();
pt.Sm();
}
static void Solve() {
var n=sc.I;
var h=new int[n+1][];
var avl=new Avl(false,false);
var li=new List<int>();
long ans=0,z=0;
for(int i = 1;i<=n;i++) {
h[i]=sc.Ia;
int m=h[i][0];
avl.Ud(m,Min(m+z-h[i][1],avl.Hs(m).d));
ans+=h[i][1]+m;
long d=inf;
while(li.Count>0&&li[li.Count-1]>=m){
d=Min(d,avl.Hs(li[li.Count-1]).d-li[li.Count-1]);
li.RemoveAt(li.Count-1);
}
avl.Ud(m,Min(d+m,avl.Hs(m).d));
li.Add(h[i][0]);
z=avl.Rd(0,mod).d;
}
pt.Wl(ans+z);
}
}
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,long.MinValue,du);
compare=CoMax;
compare2=CoMax;
}
else{
du=new Nd(nint.MinValue,long.MaxValue,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,long.MinValue,du);
compare=CoMax;
compare2=CoMax;
}
else{
du=new Nd(nint.MinValue,long.MaxValue,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 Avls:Avl{
private readonly int m,f;
private readonly (long n,long k,long d) dv=(-1,-1,-1);
public Avls(bool bo,bool bb,int c):base(bo,bb){
m=(int)Ceiling(Log(c,2));
f=(1<<m)-1;
}
public void Ud(nint n,int k,long d){base.Ud((n<<m)+k,d);}
public bool Dl(nint n,int k){return base.Dl((n<<m)+k);}
public new (long n,long k,long d) Rd(nint a,nint b){
var e=base.Rd(a<<m,((b+1)<<m)-1);
return e!=du?(e.n>>m,e.n&f,e.d):dv;
}
public new (long n,long k,long d) Hs(nint n){
var e=base.Lb(n<<m);
return e.n>>m==n?(e.n>>m,e.n&f,e.d):dv;
}
public (long n,long k,long d) Hs(nint n,int k){
var e=base.Hs((n<<m)+k);
return e!=du?(e.n>>m,e.n&f,e.d):dv;
}
public new (long n,long k,long d) Lb(nint n){
var e=base.Lb(n<<m);
return e!=du?(e.n>>m,e.n&f,e.d):dv;
}
public new (long n,long k,long d) Ub(nint n){
var e=base.Ub(((n+1)<<m)-1);
return e!=du?(e.n>>m,e.n&f,e.d):dv;
}
public new int Rg(nint a,nint b){return base.Rg(a<<m,((b+1)<<m)-1);}
public new (long n,long k,long d) Gl(nint a,nint b,long d){
var e=base.Gl(a<<m,((b+1)<<m)-1,d);
return e!=du?(e.n>>m,e.n&f,e.d):dv;
}
public new (long n,long k,long d) Gr(nint a,nint b,long d){
var e=base.Gr(a<<m,((b+1)<<m)-1,d);
return e!=du?(e.n>>m,e.n&f,e.d):dv;
}
public long Nn(nint n,int k){return (n<<m)+k;}
}
public class Pt{
private StringBuilder sb=new StringBuilder();
public void W(int s){sb.Append(s);}
public void W(long s){sb.Append(s);}
public void W(double s){sb.Append(s);}
public void W(decimal s){sb.Append(s);}
public void W(string s){sb.Append(s);}
public void W(object s){sb.Append(s);}
public void W(string f,int s){sb.Append(s.ToString(f));}
public void W(string f,long s){sb.Append(s.ToString(f));}
public void W(string f,double s){sb.Append(s.ToString(f));}
public void W(string f,decimal s){sb.Append(s.ToString(f));}
public void Wl(int s){sb.Append(s).Append(Environment.NewLine);}
public void Wl(long s){sb.Append(s).Append(Environment.NewLine);}
public void Wl(double s){sb.Append(s).Append(Environment.NewLine);}
public void Wl(decimal s){sb.Append(s).Append(Environment.NewLine);}
public void Wl(string s){sb.Append(s).Append(Environment.NewLine);}
public void Wl(object s){sb.Append(s).Append(Environment.NewLine);}
public void Wl(string f,int s){sb.Append(s.ToString(f)).Append(Environment.NewLine);}
public void Wl(string f,long s){sb.Append(s.ToString(f)).Append(Environment.NewLine);}
public void Wl(string f,double s){sb.Append(s.ToString(f)).Append(Environment.NewLine);}
public void Wl(string f,decimal s){sb.Append(s.ToString(f)).Append(Environment.NewLine);}
public void Wl(int[] s){sb.Append(string.Join(" ",s)).Append(Environment.NewLine);}
public void Wl(long[] s){sb.Append(string.Join(" ",s)).Append(Environment.NewLine);}
public void Wl(double[] s){sb.Append(string.Join(" ",s)).Append(Environment.NewLine);}
public void Wl(string[] s){sb.Append(string.Join(" ",s)).Append(Environment.NewLine);}
public void Wl(object[] s){sb.Append(string.Join(" ",s)).Append(Environment.NewLine);}
public void Wl(){sb.Append(Environment.NewLine);}
public void Sm(){Console.Write(sb);}
}
public class Sc{
[MethodImpl(MethodImplOptions.AggressiveInlining)]
protected virtual string Rl(){return Console.ReadLine();}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
protected virtual string[] Sp(string st){return st.Split();}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private T Ct<T>(string s){return (T)Convert.ChangeType(s,typeof(T));}
public virtual int I{get{return int.Parse(Rl());}}
public virtual long L{get{return long.Parse(Rl());}}
public virtual double D{get{return double.Parse(Rl());}}
public virtual string S{get{return Rl();}}
public int[] Ia{get{return Array.ConvertAll(Sp(Rl()),int.Parse);}}
public long[] La{get{return Array.ConvertAll(Sp(Rl()),long.Parse);}}
public double[] Da{get{return Array.ConvertAll(Sp(Rl()),double.Parse);}}
public string[] Sa{get{return Sp(Rl());}}
public object[] Oa{get{return Sp(Rl());}}
public int[] Ia2{get{return Array.ConvertAll(Sp("0 "+Rl()+" 0"),int.Parse);}}
public int[] Ia3(string a,string b){return Array.ConvertAll(Sp(a+Rl()+b),int.Parse);}
public int[] Ia3(int a){return Array.ConvertAll(Sp(Rl()+" "+a.ToString()),int.Parse);}
public long[] La2{get{return Array.ConvertAll(Sp("0 "+Rl()+" 0"),long.Parse);}}
public long[] La3(string a,string b){return Array.ConvertAll(Sp(a+Rl()+b),long.Parse);}
public long[] La3(int a){return Array.ConvertAll(Sp(Rl()+" "+a.ToString()),long.Parse);}
public double[] Da2{get{return Array.ConvertAll(Sp("0 "+Rl()+" 0"),double.Parse);}}
public double[] Da3(string a,string b){return Array.ConvertAll(Sp(a+Rl()+b),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(Sp(Rl()));}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,Sp(Rl()));}return a;}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public (T,T) Tp2<T>(){var s=Sp(Rl());return (Ct<T>(s[0]),Ct<T>(s[1]));}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public (T,T,T) Tp3<T>(){var s=Sp(Rl());return (Ct<T>(s[0]),Ct<T>(s[1]),Ct<T>(s[2]));}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public (T,T,T,T) Tp4<T>(){var s=Sp(Rl());return (Ct<T>(s[0]),Ct<T>(s[1]),Ct<T>(s[2]),Ct<T>(s[3]));}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public (T,T,T,T,T) Tp5<T>(){var s=Sp(Rl());return (Ct<T>(s[0]),Ct<T>(s[1]),Ct<T>(s[2]),Ct<T>(s[3]),Ct<T>(s[4]));}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public (T,T,T,T,T,T) Tp6<T>(){var s=Sp(Rl());return (Ct<T>(s[0]),Ct<T>(s[1]),Ct<T>(s[2]),Ct<T>(s[3]),Ct<T>(s[4]),Ct<T>(s[5]));}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public (T1,T2) Tp2<T1,T2>(){var s=Sp(Rl());return (Ct<T1>(s[0]),Ct<T2>(s[1]));}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public (T1,T1,T2) Tp3<T1,T2>(){var s=Sp(Rl());return (Ct<T1>(s[0]),Ct<T1>(s[1]),Ct<T2>(s[2]));}
}
public class Scs:Sc{
private StreamReader sr;
public Scs(string t){sr=new StreamReader(t);}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
protected override string Rl(){return sr.ReadLine();}
}
public class Sc2:Sc{
private string[] sps=new string[]{" "," ","\t"};
[MethodImpl(MethodImplOptions.AggressiveInlining)]
protected override string[] Sp(string st){return st.Split(sps,StringSplitOptions.RemoveEmptyEntries);}
public override int I{get{return int.Parse(Sp(Rl())[0]);}}
public override long L{get{return long.Parse(Sp(Rl())[0]);}}
public override double D{get{return double.Parse(Sp(Rl())[0]);}}
public override string S{get{return Sp(Rl())[0];}}
}
public class Scs2:Sc2{
private StreamReader sr;
public Scs2(string t){sr=new StreamReader(t);}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
protected override string Rl(){return sr.ReadLine();}
}
public class Sct:Sc{
private List<string> li=new List<string>();
private int l=0;
public void Add(int s){li.Add(s.ToString());}
public void Add(long s){li.Add(s.ToString());}
public void Add(double s){li.Add(s.ToString());}
public void Add(string s){li.Add(s.ToString());}
public void Add(object s){li.Add(s.ToString());}
public void Add(int[] s){li.Add(string.Join(" ",s));}
public void Add(long[] s){li.Add(string.Join(" ",s));}
public void Add(double[] s){li.Add(string.Join(" ",s));}
public void Add(string[] s){li.Add(string.Join(" ",s));}
public void Add(object[] s){li.Add(string.Join(" ",s));}
protected override string Rl(){return li[l++];}
public void Clear(){li.Clear();l=0;}
}