Submission #1497791
Source Code Expand
using System.Linq;using System;class T{T L,R;long V,S,Q;int H,C;T this[int l,int r]=>N(B(this,r),l);T(T l,long v,T r,long s,long q,int h,int c){L=l;V=v;R=r;S=s;Q=q;H=h;C=c;}T(T l,long v,T r){C=1+D(l)+D(r);S=v+Z(l)+Z(r);int a=I(l),b=I(r);if(a>b+1){l=U(l);if(I(l.L)>=I(l.R)){V=l.V;L=l.L;R=new T(l.R,v,r);}else{var x=U(l.R);V=x.V;L=new T(l.L,l.V,x.L);R=new T(x.R,v,r);}}else if(b>a+1){r=U(r);if(I(r.R)>=I(r.L)){V=r.V;L=new T(l,v,r.L);R=r.R;}else{var x=U(r.L);V=x.V;L=new T(l,v,x.L);R=new T(x.R,r.V,r.R);}}else{L=l;R=r;V=v;}H=1+Math.Max(I(L),I(R));}static T Y(int[] x,int l,int r){if(l>=r)return null;var n=(l+r)/2;return J(Y(x,l,n),x[n],Y(x,n+1,r));}static long Z(T t)=>t==null?0:t.S;static T P(T t,long q)=>t==null||q==0?t:new T(t.L,t.V,t.R,t.S+t.C*q,t.Q+q,t.H,t.C);static T U(T t)=>t==null||t.Q==0?t:new T(P(t.L,t.Q),t.V+t.Q,P(t.R,t.Q),t.S,0,t.H,t.C);static int D(T t)=>t==null?0:t.C;static int I(T t)=>t==null?0:t.H;static T J(T t,T s){if(t==null)return s;if(s==null)return t;var c=D(t)-1;return J(B(t,c),N(t,c).V,s);}static T J(T t,long x,T s){int a=I(t),b=I(s);if(Math.Abs(a-b)<=1)return new T(t,x,s);return a>b?new T((t=U(t)).L,t.V,J(t.R,x,s)):new T(J(t,x,(s=U(s)).L),s.V,s.R);}static T B(T t,int r){if(t==null||0>=r)return null;t=U(t);var c=D(t.L);return r<=c?B(t.L,r):J(t.L,t.V,B(t.R,r-c-1));}static T N(T t,int l){if(t==null||l>=D(t))return null;t=U(t);var c=D(t.L);return c<l?N(t.R,l-c-1):J(N(t.L,l),t.V,t.R);}static int[] G()=>Console.ReadLine().Split().Select(int.Parse).ToArray();static void Main(){var I=G();int N=I[0],Q=I[1],a,b;var t=Y(G(),0,N);while(Q-->0){I=G();a=I[1]-1;b=I[2];if(I[0]==1)t=J(J(t[0,a],P(t[a,b],I[3])),t[b,N]);else if(I[0]==2)t=J(J(t[0,a],t[I[3]-1,I[4]]),t[b,N]);else Console.WriteLine(Z(t[a,b]));}}}
Submission Info
Submission Time |
|
Task |
D - グラフではない |
User |
selpo |
Language |
C# (Mono 4.6.2.0) |
Score |
100 |
Code Size |
1731 Byte |
Status |
AC |
Exec Time |
3318 ms |
Memory |
48804 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
100 / 100 |
Status |
|
|
Set Name |
Test Cases |
Sample |
subtask0_sample_01.txt, subtask0_sample_02.txt |
All |
subtask0_sample_01.txt, subtask0_sample_02.txt, subtask1_largerandom_t1_01.txt, subtask1_largerandom_t1_02.txt, subtask1_largerandom_t2_03.txt, subtask1_largerandom_t2_04.txt, subtask1_largespecial01.txt, subtask1_largespecial02.txt, subtask1_largespecial03.txt, subtask1_largespecial04.txt, subtask1_largespecial05.txt, subtask1_largespecial06.txt, subtask1_smallrandom_01.txt, subtask1_smallrandom_02.txt, subtask1_smallrandom_03.txt, subtask1_smallrandom_04.txt, subtask1_smallrandom_05.txt, subtask1_smallrandom_06.txt, subtask1_smallrandom_07.txt, subtask1_smallrandom_08.txt, subtask1_smallrandom_09.txt, subtask1_smallrandom_10.txt |
Case Name |
Status |
Exec Time |
Memory |
subtask0_sample_01.txt |
AC |
24 ms |
13396 KB |
subtask0_sample_02.txt |
AC |
24 ms |
13396 KB |
subtask1_largerandom_t1_01.txt |
AC |
3318 ms |
43960 KB |
subtask1_largerandom_t1_02.txt |
AC |
3301 ms |
46008 KB |
subtask1_largerandom_t2_03.txt |
AC |
3122 ms |
45948 KB |
subtask1_largerandom_t2_04.txt |
AC |
3132 ms |
42000 KB |
subtask1_largespecial01.txt |
AC |
2352 ms |
46152 KB |
subtask1_largespecial02.txt |
AC |
2075 ms |
43960 KB |
subtask1_largespecial03.txt |
AC |
1525 ms |
44500 KB |
subtask1_largespecial04.txt |
AC |
2086 ms |
44956 KB |
subtask1_largespecial05.txt |
AC |
1833 ms |
48804 KB |
subtask1_largespecial06.txt |
AC |
978 ms |
18644 KB |
subtask1_smallrandom_01.txt |
AC |
25 ms |
11348 KB |
subtask1_smallrandom_02.txt |
AC |
25 ms |
13396 KB |
subtask1_smallrandom_03.txt |
AC |
24 ms |
9300 KB |
subtask1_smallrandom_04.txt |
AC |
24 ms |
11348 KB |
subtask1_smallrandom_05.txt |
AC |
25 ms |
13396 KB |
subtask1_smallrandom_06.txt |
AC |
25 ms |
13396 KB |
subtask1_smallrandom_07.txt |
AC |
24 ms |
9300 KB |
subtask1_smallrandom_08.txt |
AC |
25 ms |
11348 KB |
subtask1_smallrandom_09.txt |
AC |
25 ms |
13396 KB |
subtask1_smallrandom_10.txt |
AC |
25 ms |
11348 KB |