結果
| 問題 | No.631 Noelちゃんと電車旅行 |
| ユーザー |
 fgwiebfaoish
|
| 提出日時 | 2020-01-27 02:32:15 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
AC
|
| 実行時間 | 579 ms / 2,000 ms |
| コード長 | 6,414 bytes |
| コンパイル時間 | 1,588 ms |
| コンパイル使用メモリ | 109,440 KB |
| 実行使用メモリ | 48,512 KB |
| 最終ジャッジ日時 | 2024-10-02 09:44:37 |
| 合計ジャッジ時間 | 10,358 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 21 |
コンパイルメッセージ
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.IO;using System.Reflection;using static System.Math;using System.Numerics;static class Program{const int mod=(int)1e9+7;static void Main(){Sc sc=new Sc();var n=sc.I;var a=sc.Ia;var m=sc.I;var avl=new Avl2(true);avl.Ud(0,n,0);for(int i = 0;i<n-1;i++) {avl.Ud(i,i,a[i]-i*3);}int p=(n-1)*3;StringBuilder sb=new StringBuilder();for(int i = 0;i<m;i++) {var e=sc.Ia;e[0]--;e[1]--;avl.Ud(e[0],e[1],e[2]);sb.Append((p+avl.Get(0,n))+"\n");}Console.Write(sb);}}public class Avl2{public class Nd{public int h=1,c=1;public int nl,nr;public long d,dd=0;public Nd l,r;public bool lf;public Nd(int nl,int nr,long d,Nd du){this.nl=nl;this.nr=nr;this.d=d;l=du;r=du;lf=true;}public Nd(int nl,int nr,Nd l,Nd r){this.nl=nl;this.nr=nr;this.l=l;this.r=r;compare(this);h=Max(l.h,r.h)+1;lf=false;}}public Nd root,du;public int cnt=0;private static Action<Nd> compare;private static Func<long,long,long> compare2;public Avl2(bool bo){if(bo){compare=CoMax;compare2=CoMax2;}else{compare=CoMin;compare2=CoMin2;}du=new Nd(int.MinValue,int.MaxValue,bo?int.MinValue:int.MaxValue,du);du.h=0;du.c=0;root=du;}private void CoMax(Nd nd){if(nd.l.d+nd.l.dd>nd.r.d+nd.r.dd){nd.d=nd.l.d+nd.l.dd;}else{nd.d=nd.r.d+nd.r.dd;}}private void CoMin(Nd nd){if(nd.l.d+nd.l.dd<nd.r.d+nd.r.dd){nd.d=nd.l.d+nd.l.dd;}else{nd.d=nd.r.d+nd.r.dd;}}private long CoMax2(long a,long b){return Max(a,b);}private long CoMin2(long a,long b){return Min(a,b);}public void Ud(int a,int b,long d){if(a>b){a^=b;b^=a;a^=b;}if(root!=du){root=Fu(root,a,b,d);if(Abs(root.l.h-root.r.h)>1){root=Rotate(root);}}else{root=new Nd(a,b,d,du);}}private Nd Fu(Nd t,int nl,int nr,long d){Fdd(t);if(!t.lf){if(t.nl==nl&&t.nr==nr){t.d+=d;t.l.dd+=d;t.r.dd+=d;return t;}if(t.l.nr>=nl){t.l=Fu(t.l,nl,Min(t.l.nr,nr),d);}if(t.l.nr<nr){t.r=Fu(t.r,Max(t.l.nr+1,nl),nr,d);}if(Abs(t.l.l.h-t.l.r.h)>1){t.l=Rotate(t.l);}if(Abs(t.r.l.h-t.r.r.h)>1){t.r=Rotate(t.r);}compare(t);t.nl=t.l.nl;t.nr=t.r.nr;t.h=Max(t.l.h,t.r.h)+1;}else{if(t.nr<nl){return new Nd(t.nl,nr,t,new Nd(nl,nr,d,du));}else if(t.nl>nr){return new Nd(nl,t.nr,new Nd(nl,nr,d,du),t);}else if(t.nl<nl){if(t.nr<nr){Nd e=new Nd(t.nl,nr,t,new Nd(nl,nr,new Nd(nl,t.nr,t.d+d,du),new Nd(t.nr+1,nr,d,du)));t.nr=nl-1;return e;}else if(t.nr>nr){Nd e=new Nd(t.nl,t.nr,t,new Nd(nl,t.nr,new Nd(nl,nr,t.d+d,du),new Nd(nr+1,t.nr,t.d,du)));t.nr=nl-1;return e;}else{t.nr=nl-1;return new Nd(t.nl,nr,t,new Nd(nl,nr,t.d+d,du));}}else if(t.nl>nl){if(t.nr<nr){Nd e=new Nd(nl,nr,new Nd(nl,t.nl-1,d,du),new Nd(t.nl,nr,t,new Nd(t.nr+1,nr,d,du)));t.d+=d;return e;}else if(t.nr>nr){Nd e=new Nd(nl,t.nr,new Nd(nl,t.nl-1,d,du),new Nd(t.nl,t.nr,new Nd(t.nl,nr,t.d+d,du),t));t.nl=nr+1;return e;}else{t.d+=d;return new Nd(nl,nr,new Nd(nl,t.nl-1,d,du),t);}}else{if(t.nr<nr){t.d+=d;return new Nd(nl,nr,t,new Nd(t.nr+1,nr,d,du));}else if(t.nr>nr){t.nl=nr+1;return new Nd(nl,t.nr,new Nd(nl,nr,t.d+d,du),t);}else{t.d+=d;return t;}}}return t;}public long Get(int a,int b){return Fdg(root,a,b);}private long Fdg(Nd t,int nl,int nr){Fdd(t);if(t.lf){return t.d;}if(nl<=t.nl&&nr>=t.nr){return t.d;}long d=du.d;if(t.l.nr>=nl){d=Fdg(t.l,nl,nr);}if(t.r.nl<=nr){d=compare2(d,Fdg(t.r,nl,nr));}return d;}private void Fdd(Nd t){if(t.dd!=0){t.d+=t.dd;t.l.dd+=t.dd;t.r.dd+=t.dd;t.dd=0;}}private Nd Rotate(Nd t){Nd nd=du;Fdd(t);if(t.l.h>t.r.h){Fdd(t.l);if(t.l.l.h>t.l.r.h){nd=t.l;t.l=t.l.r;nd.r=t;Ft(t);}else{Fdd(t.l.r);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{Fdd(t.r);if(t.r.l.h>t.r.r.h){Fdd(t.r.l);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){if(!t.lf){t.h=Max(t.l.h,t.r.h)+1;t.c=t.l.c+t.r.c;compare(t);t.nl=t.l.nl;t.nr=t.r.nr;}}}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(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),int.Parse);}public int[] Ia3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split(),int.Parse);}public long[] La2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),long.Parse);}}public long[] La3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),long.Parse);}public long[] La3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split(),long.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;}}