結果

問題 No.728 ギブ and テイク
ユーザー fgwiebfaoishfgwiebfaoish
提出日時 2020-03-31 15:30:46
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 2,195 ms / 3,000 ms
コード長 6,794 bytes
コンパイル時間 2,764 ms
コンパイル使用メモリ 106,460 KB
実行使用メモリ 332,916 KB
最終ジャッジ日時 2023-09-06 23:31:00
合計ジャッジ時間 23,821 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 63 ms
20,976 KB
testcase_01 AC 62 ms
20,992 KB
testcase_02 AC 63 ms
23,012 KB
testcase_03 AC 63 ms
23,024 KB
testcase_04 AC 63 ms
21,000 KB
testcase_05 AC 63 ms
20,908 KB
testcase_06 AC 63 ms
21,020 KB
testcase_07 AC 63 ms
23,028 KB
testcase_08 AC 72 ms
21,180 KB
testcase_09 AC 63 ms
22,996 KB
testcase_10 AC 63 ms
20,920 KB
testcase_11 AC 70 ms
21,068 KB
testcase_12 AC 71 ms
21,176 KB
testcase_13 AC 145 ms
40,476 KB
testcase_14 AC 213 ms
53,860 KB
testcase_15 AC 123 ms
37,220 KB
testcase_16 AC 200 ms
48,700 KB
testcase_17 AC 189 ms
46,048 KB
testcase_18 AC 1,582 ms
240,308 KB
testcase_19 AC 1,685 ms
252,916 KB
testcase_20 AC 1,958 ms
293,760 KB
testcase_21 AC 1,700 ms
270,160 KB
testcase_22 AC 678 ms
121,352 KB
testcase_23 AC 431 ms
82,916 KB
testcase_24 AC 1,293 ms
202,400 KB
testcase_25 AC 1,318 ms
200,104 KB
testcase_26 AC 643 ms
112,996 KB
testcase_27 AC 2,195 ms
332,560 KB
testcase_28 AC 1,852 ms
332,916 KB
testcase_29 AC 63 ms
20,884 KB
testcase_30 AC 63 ms
24,960 KB
testcase_31 AC 62 ms
18,980 KB
testcase_32 AC 63 ms
20,900 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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.IO;
using System.Reflection;
using static System.Math;
using System.Numerics;
static class Program{
	const int mod=(int)1e9+7;
	const double eps=1e-11;
	static void Main(){
		Sc sc=new Sc();
		var n=sc.I;
		var a=sc.Ia;
		var h=new int[n][];
		Fc2 fc=new Fc2();
		for(int i = 0;i<n;i++) {
			var e=sc.Ia;
			h[i]=new int[]{a[i]-e[0],a[i],a[i]+e[1]};
			fc.Ud(a[i],a[i]+e[1],1);
		}
		long ans=0;
		for(int i = 0;i<n;i++) {
			ans+=fc.Get(h[i][0],h[i][1]-1,h[i][1],int.MaxValue-1);
		}
		Console.WriteLine("{0}",ans);
	}
}
public class Fc2{
	public class Nd{
		public int h,m,x;
		public Nd l,r;
		public int[] dat1,dat2,dat3;
		public long[] dat4;
		public bool lf;
		public Nd(int x,Nd l,Nd r){this.x=x;this.l=l;this.r=r;lf=false;h=2;}
		public Nd(int x){this.x=x;lf=true;h=1;}
		public virtual void Ad(int y,long d){}
	}
	public class Nd1:Nd{
		public List<Tuple<int,long>> li=new List<Tuple<int,long>>();
		public Nd1(int x,int y,long d,Nd du):base(x){
			li.Add(Tuple.Create(y,d));
			l=r=du;
		}
		public override void Ad(int y,long d){li.Add(Tuple.Create(y,d));}
	}
	public Nd root,du;
	public int cnt=0;
	private bool bo=false;
	public Fc2(){
		du=new Nd(int.MinValue);du.h=0;
		root=du;
	}
	public void Ud(int x,int y,long d){
		if(!root.lf){
			Fu(root,x,y,d);
			if(Abs(root.l.h-root.r.h)>1){root=Rotate(root);}
		}
		else if(root!=du){
			if(root.x!=x){root=Flf(root,x,y,d);}
			else{root.Ad(y,d);}
		}
		else{root=new Nd1(x,y,d,du);}
		cnt++;
	}
	private void Fu(Nd t,int x,int y,long d){
		if(t.x>x){
			if(!t.l.lf){
				Fu(t.l,x,y,d);
				if(Abs(t.l.l.h-t.l.r.h)>1){t.l=Rotate(t.l);}
			}
			else if(t.l.x!=x){t.l=Flf(t.l,x,y,d);}
			else{t.l.Ad(y,d);}
		}
		else{
			if(!t.r.lf){
				Fu(t.r,x,y,d);
				if(Abs(t.r.l.h-t.r.r.h)>1){t.r=Rotate(t.r);}
			}
			else if(t.r.x!=x){t.r=Flf(t.r,x,y,d);}
			else{t.r.Ad(y,d);}
		}
		t.h=Max(t.l.h,t.r.h)+1;
	}
	private Nd Flf(Nd t,int x,int y,long d){
		var e=new Nd1(x,y,d,du);
		return t.x>x?new Nd(t.x,e,t):new Nd(x,t,e);
	}
	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){
		if(!t.lf){t.h=Max(t.l.h,t.r.h)+1;}
	}
	public long Get(int x1,int x2,int y1,int y2){
		if(!bo){Dn();}
		int lb=-1,ub=root.dat1.Length,mid=0;
		while(ub-lb>1){
			mid=(ub+lb)>>1;
			if(root.dat1[mid]>y2){ub=mid;}
			else{lb=mid;}
		}
		int p=ub;
		lb=-1;ub=root.dat1.Length;
		while(ub-lb>1){
			mid=(ub+lb)>>1;
			if(root.dat1[mid]>=y1){ub=mid;}
			else{lb=mid;}
		}
		return Fdg(root,x1,x2,false,false,ub,p);
	}
	private long Fdg(Nd t,int a,int b,bool l,bool r,int la,int ra){
		if(t.lf){
			if(a<=t.x&&t.x<=b){return t.dat4[ra]-t.dat4[la];}
			else{return 0;}
		}
		if(l&&r){return t.dat4[ra]-t.dat4[la];}
		if(t.x>b){return Fdg(t.l,a,b,l,t.x<=b,t.dat2[la],t.dat2[ra]);}
		if(t.x<a){return Fdg(t.r,a,b,t.x>=a,r,t.dat3[la],t.dat3[ra]);}
		return Fdg(t.l,a,b,l,t.x<=b,t.dat2[la],t.dat2[ra])+Fdg(t.r,a,b,t.x>=a,r,t.dat3[la],t.dat3[ra]);
	}
	private void Dn(){
		Fu(root);
		bo=true;
	}
	private void Fu(Nd t){
		if(t.lf){
			var z=(Nd1)t;
			z.li.Sort((u,v)=>u.Item1-v.Item1);
			z.m=z.li.Count;
			z.dat1=new int[z.m];
			z.dat4=new long[z.m+1];
			for(int i = 0;i<z.m;i++) {
				z.dat1[i]=z.li[i].Item1;
				z.dat4[i+1]=z.dat4[i]+z.li[i].Item2;
			}
			return;
		}
		Fu(t.l);
		Fu(t.r);
		t.m=t.l.m+t.r.m;
		t.dat1=new int[t.m+1];
		t.dat2=new int[t.m+1];
		t.dat3=new int[t.m+1];
		t.dat4=new long[t.m+1];
		int j=0,k=0;
		long gl=0,gr=0;
		while(j<t.l.m&&k<t.r.m){
			if(t.l.dat1[j]<t.r.dat1[k]){
				t.dat1[j+k]=t.l.dat1[j];
				t.dat4[j+k+1]=t.l.dat4[j+1]+gr;
				gl=t.l.dat4[j+1];
				j++;
			}
			else{
				t.dat1[j+k]=t.r.dat1[k];
				t.dat4[j+k+1]=t.r.dat4[k+1]+gl;
				gr=t.r.dat4[k+1];
				k++;
			}
			t.dat2[j+k]=j;
			t.dat3[j+k]=k;
		}
		while(j<t.l.m){
			t.dat1[j+k]=t.l.dat1[j];
			t.dat2[j+k]=j;
			t.dat3[j+k]=k;
			t.dat4[j+k+1]=t.l.dat4[j+1]+gr;
			j++;
		}
		while(k<t.r.m){
			t.dat1[j+k]=t.r.dat1[k];
			t.dat2[j+k]=j;
			t.dat3[j+k]=k;
			t.dat4[j+k+1]=t.r.dat4[k+1]+gl;
			k++;
		}
		t.dat1[j+k]=int.MaxValue;
		t.dat2[j+k]=j;
		t.dat3[j+k]=k;
	}
}
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 double[] Da2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),double.Parse);}}
	public double[] Da3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),double.Parse);}
	public double[] Da3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).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;}
}
0