結果
| 問題 | No.876 Range Compress Query |
| ユーザー |
 fgwiebfaoish
|
| 提出日時 | 2020-02-18 04:56:06 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 5,254 bytes |
| コンパイル時間 | 1,155 ms |
| コンパイル使用メモリ | 113,820 KB |
| 実行使用メモリ | 60,504 KB |
| 最終ジャッジ日時 | 2024-10-06 15:23:22 |
| 合計ジャッジ時間 | 7,935 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| 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.Ia3(0);St st=new St(a);StringBuilder sb=new StringBuilder();for(int i = 0;i<s[1];i++) {var e=sc.Ia;if(e[0]==1){st.Ud2(e[1],e[2],e[3]);}else{sb.Append(st.Get(e[1],e[2]).d1+"\n");}}Console.Write(sb);}}public class Dt{public static int e=0;public int d1;public long c1,l,r;static Dt(){}public Dt(bool b){d1=e;c1=0;}public Dt(int d1,long l,long r){this.d1=d1;this.l=l;this.r=r;c1=0;}public Dt(Dt e){d1=e.d1;c1=0;}public static Dt Um(Dt a,long n){a.l+=n;a.r+=n;return a;}public static Dt Dm(Dt a,long n){a.c1+=n;return a;}public static Dt Cm(Dt a,Dt b){if(b.d1==0){return a;}var e=new Dt(a.d1+b.d1,a.l,b.r);if(a.r==b.l){e.d1--;}return e;}public static bool operator==(Dt a,Dt b){return a.d1==b.d1;}public static bool operator!=(Dt a,Dt b){return a.d1!=b.d1;}public override bool Equals(object obj){return false;}public override int GetHashCode(){return 0;}}public class St{public Dt[] dat;private int m=1,cnt;private Dt du;public St(int n){du=new Dt(true);while(m<n){m<<=1;}m--;cnt=m+n;dat=new Dt[cnt+1];dat[cnt]=du;for(int i=cnt-1;i>=m;i--){dat[i]=new Dt(true);}for(int i=m-1;i>=0;i--){dat[i]=(i<<1)+1<m+n?dat[(i<<1)+1]:du;}}public St(int[] a){int n=a.Length;du=new Dt(true);while(m<n){m<<=1;}m--;cnt=m+n;dat=new Dt[cnt+1];dat[cnt]=du;for(int i=cnt-1;i>=m;i--){dat[i]=new Dt(1,a[i-m],a[i-m]);}for(int i=m-1;i>=0;i--){if((i<<1)+2<cnt){dat[i]=Dt.Cm(dat[(i<<1)+1],dat[(i<<1)+2]);}else if((i<<1)+1<m+n){dat[i]=dat[(i<<1)+1];}else{dat[i]=du;}}}public void Ud(int q,long b1){q+=m;dat[q]=Dt.Um(dat[q],b1);q=(q-1)>>1;while(q>=0){Dt o=Dt.Cm(dat[(q<<1)+1],dat[(q<<1)+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(dat[k].c1!=0){Fde(k,Dt.e);}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 Dt.Cm(p,q);}public Dt Get(int a,int b){return a>b?du:Fdg(a,b,0,0,m);}public void Ud2(int a,int b,long d){Hn(a,b,0,0,m,d);}private void Hn(int a,int b,int k,int l,int r,long d){if(a<=l&&r<=b){Fde(k,d);return;}else if(dat[k].c1!=0){Fde(k,Dt.e);}if(r>=a&&b>=l){Hn(a,b,k*2+1,l,(l+r)>>1,d);Hn(a,b,k*2+2,(l+r+1)>>1,r,d);dat[k]=Dt.Cm(dat[(k<<1)+1],dat[(k<<1)+2]);}}private void Fde(int k,long d){dat[k]=Dt.Dm(dat[k],d);dat[k]=Dt.Um(dat[k],dat[k].c1);if((k<<1)+2<=cnt){dat[(k<<1)+1]=Dt.Dm(dat[(k<<1)+1],dat[k].c1);}if((k<<1)+2<cnt){dat[(k<<1)+2]=Dt.Dm(dat[(k<<1)+2],dat[k].c1);}dat[k].c1=Dt.e;}}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;}}