結果
| 問題 | No.878 Range High-Element Query |
| ユーザー |
 fgwiebfaoish
|
| 提出日時 | 2020-02-18 22:56:12 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 4,844 bytes |
| コンパイル時間 | 866 ms |
| コンパイル使用メモリ | 111,360 KB |
| 実行使用メモリ | 40,192 KB |
| 最終ジャッジ日時 | 2024-10-06 15:52:25 |
| 合計ジャッジ時間 | 4,946 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | WA * 18 |
コンパイルメッセージ
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;var a=sc.Ia;St st=new St(s[0]+1,true,false,0);Bit bit=new Bit(s[0]);var h=sc.Arr(s[1],i=>sc.Ia3(i));Array.Sort(h,(u,v)=>u[2]-v[2]);int p=0;var ans=new int[s[1]];int j=0;for(int i = 0;i<s[0];i++) {int g=(int)st.Get(a[i],s[0]).d;if(p!=g){while(j<s[1]&&h[j][2]<=g){ans[h[j][0]]=(int)bit.Get2(h[j][2],h[j][3]);j++;}p=g;}bit.Ud(i+1,1);st.Ud(a[i],i+1);}while(j<s[1]){ans[h[j][0]]=(int)bit.Get2(h[j][2],h[j][3]);j++;}Console.WriteLine("{0}",String.Join("\n",ans));}}public class Bit{private int n;private long[] bit;public Bit(int n){this.n=n;bit=new long[n+1];}public void Ud(int a,long p){while(a<=n){bit[a]+=p;a+=a&-a;}}public long Get(int n){long a=0;while(n>0){a+=bit[n];n-=n&-n;}return a;}public long Get2(int m,int n){long a=0,b=0;m--;while(n>m){a+=bit[n];n-=n&-n;}if(n==m){return a;}while(n!=m){b+=bit[m];m-=m&-m;}return a-b;}public void Clear(){bit=new long[n+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 override string ToString()=>"n:"+n.ToString()+" d:"+d.ToString();}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 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;}}