結果
問題 | No.953 席 |
ユーザー |
![]() |
提出日時 | 2019-12-16 02:54:11 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 672 ms / 2,000 ms |
コード長 | 6,065 bytes |
コンパイル時間 | 1,092 ms |
コンパイル使用メモリ | 110,592 KB |
実行使用メモリ | 44,920 KB |
最終ジャッジ日時 | 2024-07-02 19:03:25 |
合計ジャッジ時間 | 16,951 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 25 |
コンパイルメッセージ
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 s=sc.Ia; int p=s[1]; var o=new int[]{s[1]-s[2],s[2]-s[1]}; var b=true; St st=new St(s[0]+2,false,true,0); for(int i = 1,j=0;;i++) { p+=i*o[i&1]; if(p>0&&p<=s[0]){ j++; st.Ud(p,j); b=true; } else if(b){b=false;} else{break;} } var pq=new Pq<Dt<Tuple<int,long>>>(32,true); var n=sc.I; for(int i = 0;i<n;i++) { var e=sc.La; pq.Push(new Dt<Tuple<int,long>>(e[0]*2+1,Tuple.Create(i,e[1]*2))); } var d=new int[n]; var r=new int[s[0]+2]; var g=new Dt<Tuple<int,long>>[n+1]; int k=0,l=0; while(pq.cnt>0){ var e=pq.Top; pq.Pop(); if(e.d.Item2!=-1){ if(st.Get(1,s[0]).d>=1e9){ g[k]=e; k++; continue; } int z=st.Get(1,s[0]).n; st.Ud(z,(long)1e9); if(r[z+1]==0){st.Ud(z+1,200000);} if(r[z-1]==0){st.Ud(z-1,200000);} r[z+1]++; r[z-1]++; pq.Push(new Dt<Tuple<int,long>>((e.n+e.d.Item2)&-2,Tuple.Create(e.d.Item1,-1L))); d[e.d.Item1]=z; } else{ int z=d[e.d.Item1]; st.Ud(z,(long)-1e9); r[z+1]--; r[z-1]--; if(r[z+1]==0){st.Ud(z+1,-200000);} if(r[z-1]==0){st.Ud(z-1,-200000);} } if((pq.cnt==0||pq.Top.n!=e.n)){ while(g[l]!=null&&st.Get(1,s[0]).d<1e9){ int z=st.Get(1,s[0]).n; st.Ud(z,(long)1e9); if(r[z+1]==0){st.Ud(z+1,200000);} if(r[z-1]==0){st.Ud(z-1,200000);} r[z+1]++; r[z-1]++; pq.Push(new Dt<Tuple<int,long>>((e.n+g[l].d.Item2)&-2,Tuple.Create(g[l].d.Item1,-1L))); d[g[l].d.Item1]=z; l++; } } } Console.WriteLine(String.Join("\n",d)); } } public class Dt<T>:IComparable{ public long n; public T d; public Dt(long n,T d){this.n=n;this.d=d;} public int CompareTo(object obj){ Dt<T> mymo=(Dt<T>)obj; if(mymo.n>n){return -1;} else if(mymo.n<n){return 1;} else{return 0;} } } public class Pq<T> where T:IComparable{ private T[] he; public int cnt=0,max=0; private Func<T,T,int> compare; public Pq(int max,bool mm){ this.max=max; he=new T[max]; if(mm){compare=Ao;} else{compare=Do;} } public void Push(T x){ if(cnt==max){Extend();} int j=cnt; while(j!=0&&compare(x,he[(j-1)>>1])>0){he[j]=he[(j-1)>>1];j=(j-1)>>1;} he[j]=x; cnt++; } public void Pop(){ cnt--; T r=he[cnt]; int j=0; while(true){ if(j*2+1<cnt){ if(compare(he[j*2+1],he[j*2+2])>0){j=j*2+1;} else{j=j*2+2;} } else if(j*2<cnt){j=j*2+1;} else{break;} if(compare(he[j],r)<=0){j=(j-1)>>1;break;} he[(j-1)>>1]=he[j]; } he[j]=r; } private int Ao(T x,T y){return y.CompareTo(x);} private int Do(T x,T y){return x.CompareTo(y);} public T Top{get{return he[0];}} private void Extend(){ T[] nhe=new T[max<<1]; Array.Copy(he,nhe,max); he=nhe; max<<=1; } } public class St{ public class Dt{ public int n; public long d; public Dt(long d,int n){this.d=d;this.n=n;} } public Dt[] dat; private int m=1; private bool mm,ku; private Dt du; private Func<Dt,Dt,bool> compare; public St(int n,bool mm,bool ku,long df){ this.mm=mm;this.ku=ku; if(mm){du=new Dt(long.MinValue,-1);compare=CoMax;} else{du=new Dt(long.MaxValue,-1);compare=CoMin;} while(m<n){m<<=1;} m--; dat=new Dt[m+n+1]; dat[m+n]=du; for(int i=m+n-1;i>=m;i--){dat[i]=new Dt(df,i-m);} for(int i=m-1;i>=0;i--){dat[i]=(i<<1)+1<m+n?dat[(i<<1)+1]:du;} } private bool CoMax(Dt x,Dt y){return x.d>y.d;} private bool CoMin(Dt x,Dt y){return x.d<y.d;} public void Ud(int q,long b){ q+=m; if(ku){b+=dat[q].d;} dat[q].d=du.d; dat[q]=new Dt(b,q-m); q=(q-1)>>1; while(q>=0){ Dt o=compare(dat[2*q+1],dat[2*q+2])?dat[2*q+1]:dat[2*q+2]; if(dat[q]==o){break;} dat[q]=o; q=(q-1)>>1; } } private Dt Fdg(int a,int b,int k,int l,int r){ if(r<a||b<l){return du;} if(a<=l&&r<=b){return dat[k];} Dt p=Fdg(a,b,k*2+1,l,(l+r)>>1); Dt q=Fdg(a,b,k*2+2,(l+r+1)>>1,r); return compare(p,q)?p:q; } public Dt Get(int a,int b){return Fdg(a,b,0,0,m);} } 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;} }